首页 > 代码库 > uva 10692 - Huge Mods(数论)
uva 10692 - Huge Mods(数论)
题目链接:uva 10692 - Huge Mods
题目大意:给出一个数的次方形式,就它模掉M的值。
解题思路:根据剩余系的性质,最后一定是行成周期的,所以就有ab=abmod(phi[M])+phi[M](phi[M]为M的欧拉函数),这样就可以根据递归去求解。
#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn = 15;
int A[maxn], k;
int pow_mod (int a, int n, int M) {
int ans = 1;
while (n) {
if (n&1)
ans = ans * a % M;
a = a * a % M;
n /= 2;
}
return ans;
}
int euler_phi(int n) {
int m = (int)sqrt(n+0.5);
int ans = n;
for (int i = 2; i <= m; i++) {
if (n % i == 0) {
ans = ans / i * (i-1);
while (n%i==0)
n /= i;
}
}
if (n > 1)
ans = ans / n * (n - 1);
return ans;
}
int solve (int d, int M) {
if (d == k - 1)
return A[d]%M;
int phi = euler_phi(M);
int c = solve (d+1, phi) + phi;
return pow_mod(A[d], c, M);
}
int main () {
int cas = 1;
char str[maxn];
while (scanf("%s", str) == 1 && strcmp(str, "#")) {
int M;
sscanf(str, "%d", &M);
scanf("%d", &k);
for (int i = 0; i < k; i++)
scanf("%d", &A[i]);
printf("Case #%d: %d\n", cas++, solve(0, M));
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。