求大数高次幂的模

2019-04-13 22:05发布

站内文章 / 模拟电子
17619 0 1234
题目：

/* 球大数高次幂的模 X^Y mod Z 思路： x^y mod z = (x % z)*(x % z)*、、、*(x % z) */ #include bool Getmi(int X, int Y, int Z, int &res) { int numl(1); int numy(Y); int multi(X); int tmp(0); int tres(1); multi = multi % Z; if(multi > 1) //当余数等于0、1时直接可求得结果 while(numy > 0) { if(multi == 1)break;//当余数等于1时结束循环 numl = 1; int tt = numy; X = multi; while(X < Z && tt > 0 ) { X *= multi; tt--; numl++; } tmp = numy % numl; while(tmp) { if(multi == 1)break; tres *= multi; tmp--; } multi = X % Z; numy = numy / numl; tres %= Z; } res = (multi * tres) % Z; return true; } int main() { int x, y, z; int res(0); while(1) { res = 0; printf("请输入x, y, z:"); scanf("%d %d %d", &x, &y, &z); if(Getmi(x, y, z, res)) { printf("result = %d ", res); } else { printf("Wrong!!! "); } } } 测试结果：

热门文章