洛谷 4296 [AHOI2007]密码箱 题解

题意简述

给定$n$，输出所有的整数$x$满足：$0<x<n$且$x^2=1 (mod n)$。

n<=2e9.

思路

以下所有的$=$都表示同余（那个三条横线我不会打…）

$x^2=1 (mod n)$
$x^2-1=0 (mod n)$
$(x-1)(x+1)=0 (mod n)$

枚举一对$a,b$使得$ab=n$。（按对枚举因数）

然后枚举$x$使得：$x-1$是$a$的倍数且$x+1$是$b$的倍数，或者$x-1$是$b$的倍数且$x+1$是$a$的倍数。用$set$去一下重。

时间复杂度是O(n所有小于$\sqrt{n}$的因数的和，然后乘一个logn)。反正是能过的吧。

代码

复制

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }

    int n;
    void Input()
    {
        R1(n);
    }

    set<int> ans;
    void Soviet()
    {
        for(int a=1;a*a<=n;++a) if (n%a==0) //枚举a
        {
            int b=n/a; //枚举b (b>a)
            for(int x=1;x<=n;x+=b) if ((x+1)%a==0) ans.insert(x);
            //case1 (x-1)%b==0 and (x+1)%a==0
            for(int x=b-1;x<=n;x+=b) if ((x-1)%a==0) ans.insert(x); 
            //case2 (x-1)%a==0 and (x+1)%b==0
        }
        while(!ans.empty())
        {
            printf("%d\n",*ans.begin());
            ans.erase(ans.begin());
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}