「BZOJ1406」[AHOI2007] 密码箱
Description
在一次偶然的情况下，小可可得到了一个密码箱，听说里面藏着一份古代流传下来的藏宝图，只要能破解密码就能打开箱子，而箱子背面刻着的古代图标，就是对密码的提示。经过艰苦的破译，小可可发现，这些图标表示一个数以及这个数与密码的关系。假设这个数是n，密码为x，那么可以得到如下表述： 密码x大于等于0，且小于n，而x的平方除以n，得到的余数为1。 小可可知道满足上述条件的x可能不止一个，所以一定要把所有满足条件的x计算出来，密码肯定就在其中。计算的过程是很艰苦的，你能否编写一个程序来帮助小可可呢？（题中ｘ，ｎ均为正整数）
Input
输入文件只有一行，且只有一个数字n(1<=n<=2,000,000,000)。
Output
你的程序需要找到所有满足前面所描述条件的x，如果不存在这样的x，你的程序只需输出一行“None”(引号不输出)，否则请按照从小到大的顺序输出这些x，每行一个数。
Sample Input
12
Sample Output
1
5
7
11
5
7
11
HINT
求所有的x
kn=x^2-1
kn=(x-1)*(x+1)
枚举n的所有约数d>√n，事实上远不及√n
d|(x-1) 或 d|(x+1)
再枚举这样的x
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int top,st[200005]; vector<int> res; int main() { n=read(); for(int i=1;i*i<=n;i++) if(n%i==0) st[++top]=n/i; while(top) { int now=st[top--]; for(int i=now;i<=n;i+=now) { if((i-2)%(n/now)==0) res.push_back(i-1); if((i+2)%(n/now)==0) res.push_back(i+1); } } sort(res.begin(),res.end()); int tot=unique(res.begin(),res.end())-res.begin(); puts("1"); for(int i=0;i<tot;i++) if(res[i]<n&&res[i]>1)printf("%d\n",res[i]); return 0; } |
计数器 9788844
OI 课件=>
OI 课件=>
复杂度多少啊