【BZOJ 1406】 [AHOI2007]密码箱

【链接】 我是链接,点我呀:)
【题意】

在这里输入题意

【题解】

$x^2%n=1$ $x^2-1 = k*n$ $(x+1)*(x-1) % n == 0$ 设$n=a*b$ 对于所有的a,b(a < b) 如果x是符合要求的x. 那么一定会有某些a,b满足(x+1)%a==0 && (x-1)%b==0 或者 (x+1)%b==0 && (x-1)%a==0 因为a*b其实就是质因数分解之后某两个因子相乘。 而$(x+1)*(x-1)$既然是n的整数倍。 肯定n的因子它都有。 那么肯定能有上面的那两个情况出现。 则问题就变成 求出n的所有的因子a; 根据n/a求出b. 然后枚举b的倍数t 设t为(x+1)或t为(x-1) 算出相应的(x-1)值和(x+1)值 看看它们俩分别是不是a的倍数就好 使得话就把x加入到set中 最后输出set就好了。

x=1貌似不能通过这种方法算出来。
一开始就加进去就好。
(除了n==1不加

【代码】

#include <bits/stdc++.h>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;

const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};

int n;
set<int> myset;

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "r", stdin);
	#endif
    scanf("%d",&n);
    if (n>1) myset.insert(1);
    for (int i = 1;i*i <= n;i++)
        if (n%i==0)
        {
            int a = i,b = n/i;

            for (int j = b;j <= n;j+=b){ //x+1
                int x = j-1;
                if ( (x-1)%a==0){
                    myset.insert(x);
                }
            }

            for (int j = b;j < n;j+=b){//x-1
                int x = j+1;
                if (x>=n) continue;
                if ((x+1) %a==0){
                    myset.insert(x);
                }
            }
        }
    if (myset.empty()){
        puts("None");
    }else{
        for (set<int>::iterator it = myset.begin();it!=myset.end();it++){
            printf("%d
",*it);
        }
    }
	return 0;
}