[TIOJ] 1199. 神奇的模術

題目連結:http://tioj.infor.org/problems/1199

---

枚舉x並且用快速冪加速次方的地方，就可以做到$O(y log n)$了。

#include <bits/stdc++.h>
using namespace std;

int qPow(int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int a, n, y;
	while(cin>>a>>n>>y, a or n or y){
		int ans=0;
		for(int i=0;i<=y-1;i++){
			if(n==0 and i==0) continue;
			if(qPow(i, n, y)==a) ans++;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

int qPow(int a, int b, int m){
	int r=1;
	while(b){
		if(b&1) r=(r*a)%m;
		b>>=1;
		a=(a*a)%m;
	}
	return r%m;
}