TopCoder SRM 735 Div1 Medium QuadraticIdentity

これ参加してても本番気づかなかっただろうな…。
http://community.topcoder.com/stat?c=problem_statement&pm=14924

問題

正整数mが与えられる。
m未満の非負整数Xのうち、X≡X^2 (mod m)となるXを列挙せよ。

解法

上記式を書き換えると、X(X-1)がmの倍数となるものを求めることになる。

Xと(X-1)の積がmの倍数なのだから、Xがmの約数aの倍数である場合、(X-1)がm/aの倍数であればよい。
なお、Xと(X-1)は明らかに互いに素なので、aとm/aも互いに素でなければならない。

b=m/aとし、ある整数p,qに対しX=p*a、(X-1)=q*bとおくと、p*a - 1 = q*bであるp,qを求めればXが求められることがわかる。
これは良く見ると拡張ユークリッドの互除法で解ける形になっているので、p,qを実際に求めることができる。

なお、解はmの素因数がc個あるとき2^cである。
これはaが各素因数の倍数である場合とそうでない場合を考えれば自明である。
(aとbは互いに素なので、同じ素因数を持ちえない)

class QuadraticIdentity {
	public:
	ll ext_gcd(ll p,ll q,ll& x, ll& y) { // get px+qy=gcd(p,q)
		if(q==0) return x=1,y=0,p;
		ll g=ext_gcd(q,p%q,y,x);
		y-=p/q*x;
		return g;
	}

	ll hoge(ll m,ll a) {
		// ax-1=by -> ax-by=1
		ll x,y;
		ext_gcd(a,m/a,x,y);
		while(x<0) x+=m/a;
		while(x>=m/a) x-=m/a;
		return x*a;
	}
	
	vector<long long> getFixedPoints(long long m) {
		vector<ll> V(1,0);
		if(m==1) return V;
		for(ll a=1;a*a<=m;a++) if(m%a==0 && __gcd(a,m/a)==1) V.push_back(hoge(m,a)),V.push_back(hoge(m,m/a));
		sort(ALL(V));
		V.erase(unique(ALL(V)),V.end());
		while(V.back()>=m) V.pop_back();
		
		while(V.size()>500) {
			vector<ll> V2;
			for(int i=0;i<V.size();i+=2) V2.push_back(V[i]);
			V=V2;
		}
		
		return V;
	}
}

まとめ

ここら辺の整数系問題苦手。