ZJ d374 X^2 ≡ 1 (mod M)

這是一個數學題

吧

總之模運算什麼的不提了

直接說兩個性質

一：

設F為M的一個因數

若X^2 ≡ 1 (mod M)

則X^2 ≡ 1 (mod F)

二：

若M為質數

X^2 ≡ 1 (mod M)

的X值

只有 1 和 M-1

根據性質二

若M是質數就可以直接回答

若不是質數

可以用一點點有技巧的枚舉

先找出M的因數中

大於等於sqrt(m)的最小的因數

設此數為F

可知

F>=sqrt(m)

先以F為基準

找出所有X^2 ≡ 1 (mod F) 的X  (X<F)

然後將所有找出來的數

枚舉加上kF (最多加M/F次)

看看是否符合 X^2 ≡ 1 (mod M)

若是就加到答案裡

至於複雜度我不會算XD

跪求神人解答

以下附code ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,p,sq;
vector<ll> ans;
inline bool che(ll k){
 return k*k%m==1;
}
bool is_prime(){
 for(ll i=2;i<=sq;i++)
  if(m%i==0)
   return 0;
 return 1;
}
void solve(){
 ll fac=-1;
 for(ll i=sq;i>=2;i--)
  if(m%i==0){
   fac=i;
   break;
  }
 fac=m/fac;
 vector<ll> mia;
 mia.clear();
 for(ll i=1;i<fac;i++)
  if(i*i%fac==1)
   mia.push_back(i);
 for(ll i=0;i<m;i+=fac)
  for(ll j=0;j<mia.size();j++)
   if(che(i+mia[j]))
    ans.push_back(i+mia[j]);
}
void output(){
 cout<<ans.size()<<'\n';
 for(int i=0;i<ans.size();i++)
  cout<<ans[i]<<'\n';
}
int main(){
 cin>>m;
 // 先將一和二例外判掉
 if(m==1){
  cout<<"0\n";
  return 0;
 }
 else if(m==2){
  cout<<"1\n1\n";
  return 0;
 }
 sq=sqrt(m);
 if(is_prime()){ 
  cout<<"2\n";
  cout<<1<<'\n';
  cout<<m-1<<'\n';
  return 0;
 }
 solve();
 output();
}