注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1209.大幂模  

2011-12-03 00:09:32|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1209.大幂模
Time Limit: 1000 MS         Memory Limit: 65536 K
Total Submissions: 280 (51 users)         Accepted: 40 (23 users)
[ My Solution ]

Description

给出三个正整数a,m,n,其中a<=10000,m<=10^10000,n<=100000000 。求a^m mod n。

Input

首先输入一个正整数T,表示有几组数据,T<=100。
接下来每行输入三个正整数a,m,n。

Output

对每组数据输出a^m mod n 的结果。

Sample Input

2
2 3 5
2 10 7

Sample Output

3
2

Source
 
根据欧拉定理可以得到最后的结果,但是还是需要处理下的。m是高精度,不过求余很简单。最后求a^b mod n的时候精度超出了int,应该是long long的,害我WA了好多次。
  1. #include <stdio.h>    
  2. #include <string.h>   
  3. typedef long long i64;           
  4.   
  5. inline int eular(int n)           
  6. {                                 
  7.     int ret=1,i;                     
  8.     for (i=2;i*i<=n;i++)             
  9.         if (n%i==0)   
  10.         {                    
  11.             n/=i,ret*=i-1;                 
  12.             while (n%i==0)                 
  13.                 n/=i,ret*=i;                  
  14.         }                                  
  15.     if (n>1)                            
  16.         ret*=n-1;                          
  17.     return ret;                         
  18. }                                    
  19.       
  20.                                                                             
  21. inline int division(char *s, int n)                                            
  22. {                                                                        
  23.     int d = 0, i;                                                           
  24.     for (i = 0; i < strlen(s); i++)                                                                                                        
  25.         d = ((d * 10) % n + s[i] - '0') % n;                                                                                                 
  26.     return d;                                                             
  27. }                                                                        
  28.                                                                          
  29. inline i64 modExp(i64 a, i64 b, i64 n)   
  30. {   
  31.      i64 t = 1, y = a;   
  32.      while(b != 0)   
  33.      {   
  34.           if(b % 2 == 1) t = t * y % n;   
  35.           y = y * y % n;   
  36.           b = b / 2;   
  37.      }   
  38.      return t;   
  39. }   
  40.                                                                          
  41. int main()                                                               
  42. {                                                                        
  43.     int n, a, e, b, t;                                                         
  44.     char m[10001];                                                          
  45.     scanf("%d", &t);                                                        
  46.     while(t--)                                                              
  47.     {                                                                       
  48.         scanf("%d%s%d", &a, m, &n);                                            
  49.         e = eular(n);               
  50.         int temp = 0;                          
  51.         if(strlen(m) <= 9)                          
  52.         {                                            
  53.                                                         
  54.             for(int i = 0; i < strlen(m); i++)           
  55.                 temp =  temp * 10 + (m[i]-'0');           
  56.             if(temp <= e)                               
  57.                 b = temp;                                  
  58.             else                                        
  59.                 b = division(m, e) + e;                    
  60.         }                                            
  61.         else                                         
  62.                 b = division(m, e) + e;                    
  63.         i64 ans = modExp((i64)a, (i64)b, (i64)n);         
  64.         printf("%lld\n", ans);                                                                                                                                                     
  65.     }                                                                                                                                     
  66. return 0;                                                                
  67. }  
  评论这张
 
阅读(168)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017