【BZOJ 1406】【AHOI 2007】密码箱

本文主要是介绍【BZOJ 1406】【AHOI 2007】密码箱，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

设：x^2=kn+1
移项：(x+1)(x-1)=kn
令x+1=k1n1，x-1=k2n2，其中k1k2=k，n1n2=n
然后在n的因子中枚举n1，再枚举k1，判断一下是否存在k2，如果存在就是一个合法解，扔到set里面排序去重。

#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define N 100000
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
int n,n1,n2,k1,x;
set<int> s;
int main()
{scanf("%d",&n);fo(n2,1,n)if (n2*n2>n) break; else{if (n % n2) continue;n1 = n / n2;fo(k1,0,n/n1){x = n1 * k1 + 1; if (x > n) break;if ((x+1) % n2 == 0) s.insert(x);}fo(k1,1,n/n1){x = n1 * k1 - 1; if (x > n) break;if ((x-1) % n2 == 0) s.insert(x);}}if (!s.size()) printf("None\n");set<int>::iterator i;for(i = s.begin();i != s.end(); i++) printf("%d\n",*i);return 0;
}

这篇关于【BZOJ 1406】【AHOI 2007】密码箱的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---