首页 > 代码库 > 费马小定理

费马小定理

2024-08-22 15:38:51   218人阅读

upupup

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 239   Accepted Submission(s) : 14

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

最近侯ry感觉自己在数学方面的造诣不忍直视；他发现他的学习速率呈一个指数函数递增，疯狂的陷入学习的泥潭，无法自拔；他的队友发现了他的学习速率y=e^（b*lna+lnc);
e是科学界非常重要而常见的常数，e=2.718281828……。
侯ry由于数学很差不会算学习数率y，现求助于学弟，感激不尽；

Input

多组数据，每组数据输入三个整数a，b，c（a，c<=10^12,b<=10^100000)

Output

一个整数y，对10^9+7取模

Sample Input

2 3 10

Sample Output

80

　　　　费马小定理(Fermat Theory)是数论中的一个重要定理，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

　　　周末打的场比赛，里面的一道题目，用费马小定理可以分分钟秒杀hhh，这道题可以直接转化成(a^b)*c的问题，但由于b是个大数，如果看懂了费
马小定理，这时候应该就知道怎么解决了，直接用一个高精度取余单精度就可以把这个棘手的问题解决了，将b直接转化成了一个比模数10^9+7还小的数，之
后就一个快速幂就可以得到结果了，是不是很腻害的样子>.<
 1 #include<iostream>
 2 #define LL long long
 3 #define N 1000000007
 4 using namespace std;
 5 
 6 struct num
 7 {
 8     static const int L=100005;
 9     int a[L];
10     int len;
11     void ini(string s)//字符串输入
12     {
13         fill(a,a+L,0);
14         for(int i=s.length()-1;i>=0;i--)
15             a[s.length()-i-1]=s[i]-‘0‘;
16         len=s.length();
17     }
18 };
19 LL mod(num a)//高精度取余单精度 输出余数
20 {
21     LL temp=0;
22     for(int i=a.len-1; i>=0; i--)
23         temp=(temp*10+a.a[i])%(N-1);
24     return temp;
25 }
26 LL quickpow(LL m,LL n)
27 {
28     LL b = 1;
29     while (n > 0)
30     {
31           if (n & 1)
32              b = (b*m)%N;
33           n = n >> 1 ;
34           m = (m*m)%N;
35     }
36     return b;
37 }
38 int main()
39 {
40     LL a,c;
41     num str;
42     string ss;
43     while(cin>>a>>ss>>c)
44     {
45         str.ini(ss);
46         LL temp=mod(str);
47         c=c%N;
48         a%=N;
49         LL ans=(quickpow(a,temp)*c)%N;
50         cout<<ans<<endl;
51     }
52     return 0;
53 }



费马小定理


联系
我们