uva 10692 高次幂取模
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.
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, ... , aNwould 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^...^aNmod 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 |
Case #1: 2 |
题目大意:求一个数((((a^b)^c)^d)^e)..... Mod m的值
幂太huge了,上界是1000^1000^1000^1000^1000^1000^1000^1000^1000,暴力快速幂模肯定行不通,因为幂是多少都难的计算。有公式a^x=a^(x%phi(c)+phi(c)) (mod c),所以可以用递归方法求解。
AC代码:
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int phi[];
int f[],n;
string m; void init()
{
int i;
for(i=;i<=;i++) phi[i]=;
phi[]=;
for(i=;i<=;i++)
if(!phi[i])
for(int j=i;j<=;j+=i)
{
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
} int montgomery(int a,int b,int c)
{
int t=;
while(b)
{
if(b%)
t=t*a%c;
b/=;
a=a*a%c;
}
return t;
} int dfs(int now,int mod)
{
if(now==n-)
{
return f[now]%mod;
}
int t=dfs(now+,phi[mod]);
int ans=montgomery(f[now],t+phi[mod],mod);
return ans;
}
int main()
{
init();
int i,ret,kase=;
while(cin>>m,m!="#")
{
ret=;
for(i=;i<m.size();i++)
ret=ret*+m[i]-'';
cin>>n;
for(int i=;i<n;i++)
scanf("%d",f+i);
cout<<"Case #"<<kase++<<": ";
printf("%d\n",dfs(,ret));
}
return ;
}
最新文章
- JavaScript If...Else 语句
- BZOJ 3809: Gty的二逼妹子序列
- 数据库中char, varchar, nvarchar的差异
- 刷新SqlServer所有视图【存储过程】
- [Java Basics] multi-threading
- Java中的内省
- POJ 2378 Tree Cutting (DFS)
- BootStrap2学习日记22---点击展开
- SQL Server 添加登录账户配置权限
- js检测浏览器中是否安装了flash播放插件
- MySQL之删_delete-truncate
- django - 总结 - cnblog
- linux 几种服务类型
- 【vue】在移动端使用better-scroll 实现滚动效果
- AdvStringGrid常用操作
- (转载)常用正则表达式大全!(例如:匹配中文、匹配html)
- web api 跨域访问
- Eclipse/MyEclipse向HDFS中如创建文件夹等操作报错permission denied解决办法
- CentOS系统中文改英文
- jquery动态加载js/css文件方法