首页 > 代码库 > UVA - 10692 Huge Mods （欧拉函数）
UVA - 10692 Huge Mods （欧拉函数）
Problem X
Huge Mod
Input: standard input
Output: standard output
Time Limit: 1 second
The operator for exponentiation is different from the addition, subtraction, multiplication or division operators in the sense that the default associativity for exponentiation goes right to left instead of left to right. So unless we mess it up by placing parenthesis,
should mean
not
. This leads to the obvious fact that if we take the levels of exponents higher (i.e., 2^3^4^5^3), the numbers can become quite big. But let‘s not make life miserable. We being the good guys would force the ultimate value to be no more than 10000.
Given a1, a2, a3, ... , aN and m(=10000)
you only need to compute a1^a2^a3^...^aN mod m.
you only need to compute a1^a2^a3^...^aN mod m.
Input
There can be multiple (not more than 100) test cases. Each test case will be presented in a single line. The first line of each test case would contain the value for M(2<=M<=10000). The next number of that line would be N(1<=N<=10). Then N numbers - the values for a1, a2, a3, ... , aN would follow. You can safely assume that 1<=ai<=1000. The end of input is marked by a line containing a single hash (‘#‘) mark.Output
For each of the test cases, print the test case number followed by the value of a1^a2^a3^...^aN mod m on one line. The sample output shows the exact format for printing the test case number.Sample Input | Sample Output |
10 4 2 3 4 5 100 2 5 2 53 3 2 3 2 # | Case #1: 2 Case #2: 25 Case #3: 35 |
Problem setter: Monirul Hasan, Member of Elite Problemsetters‘ Panel
Special thanks: Mohammad Sajjad Hossain
题意：输入正整数a1,a2,a3..an和模m，求a1^a2^...^an mod m
思路：需要用到一个公式：
，递归处理
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
const int maxn = 1010;
int a[maxn], vis[maxn], n;
char str[maxn];
int euler_phi(int m) {
int tmp = (int) sqrt(m+0.5);
int ans = m;
for (int i = 2; i <= tmp; i++) if (m % i == 0) {
ans = ans / i * (i-1);
while (m % i == 0)
m /= i;
}
if (m > 1)
ans = ans / m * (m-1);
return ans;
}
int pow_mod(int a, int m, int mod) {
int tmp = 1;
while (m) {
if (m & 1)
tmp = tmp * a % mod;
m >>= 1;
a = a * a % mod;
}
return tmp;
}
int solve(int cur, int m) {
if (cur == n-1)
return a[cur] % m;
int phi_m = euler_phi(m);
int tmp = solve(cur+1, phi_m);
return pow_mod(a[cur], tmp + phi_m, m);
}
int main() {
int cas = 1, mod;
while (scanf("%s", str) != EOF && str[0] != '#') {
mod = 0;
for (int i = 0; str[i]; i++)
mod = mod*10 + str[i] - '0';
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Case #%d: %d\n", cas++, solve(0, mod));
}
return 0;
}UVA - 10692 Huge Mods （欧拉函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。