用一下求a^b % m的log(n)的算法就行了, 要注意范围, 要用__int64, 不然会出错
ps: 递归真是很美妙而又不容易出错的编码方式, 所以能用递归, 而且不会造成堆栈溢出的时候, 就用递归吧, 切莫为了那一点的机器时间而装逼, 装逼遭雷劈啊
#include#include #include #include using namespace std;int powAndMod(int a, int b, int m) { if (b == 1) return a % m; if (b % 2 == 0) { int h = powAndMod(a, b / 2, m); return (h * h) % m; } else { int h = powAndMod(a, (b - 1) / 2, m); return (int)(((__int64)h * h * (a % m)) % m); }}int main() { int N, M, K; int i; int x; int ans = 0; scanf("%d %d %d", &N, &M, &K); for (i = 0; i < N; ++i) { scanf("%d", &x); if (powAndMod(x, M, K) == 0) ans++; } printf("%d\n", ans); return 0;}