TLE60分
https://www.luogu.com.cn/problem/P1226
#include<bits/stdc++.h>
using namespace std;
long long x,y,z;
long long fz(long long a,long long b,long long c)
{
if(b==0) return 1;
if(b%2==1) return fz(a,b/2,c)*x%c*fz(a,b/2,c)%c;
return (fz(a,b/2,c)*fz(a,b/2,c))%c;
}
int main()
{
cin>>x>>y>>z;
cout<<x<<"^"<<y<<" mod "<<z<<"="<<fz(x,y,z);
return 0;
}
？？？？
给你几个方法：
这应该是求 a^b 的最朴素算法了，简称 慢速幂。
直接暴力乘再取模即可，代码就不给力。
当然这种算法只有 60 分：
我们可以将 p 拆解，举个栗子 3^{90}\ \%\ 17
3^{90}\ \%\ 17 可以拆分为 ((3^{45}\ \%\ 17) \times (3^{45}\ \%\ 17))\ \%\ 17
而 3^{45}\ \%\ 17 则又可以拆分为 ((3^{22}\ \%\ 17) \times (3^{22}\ \%\ 17) \times (3\ \%\ 17))\ \%\ 17
后 3^{22}\ \%\ 17 则拆分为 ((3^{11}\ \%\ 17) \times (3^{11}\ \%\ 17))\ \%\ 17
以此类推得
3^{11}\ \%\ 17 = ((3^5\ \%\ 17) \times (3^5\ \%\ 17) \times (3\ \%\ 17))\ \%\ 17
3^5\ \%\ 17 = ((3^2\ \%\ 17) \times (3^2\ \%\ 17) \times (3\ \%\ 17))\ \% \ 17
3^2\ \%\ 17= ((3\ \%\ 17) \times (3\ \%\ 17))\ \%\ 17
为了之后方便，我称以上为 “结论1”
因此可得如下 p 的变化：
| p | p / 2 |
|---|---|
| \color{Red}{90} | \color{Red}{45} |
| 45 | \color{Red}{22} |
| 22 | \color{Red}{11} |
| 11 | \color{Red}{5} |
| 5 | \color{Red}{2} |
| 2 | \color{Red}{1} |
为了提升速度，我们据上表，可知只需计算上表 \color{Red}{红色部分} ，即 3^{\color{Red}{"红色部分"}}\ \%\ 17 ，得代码如下
long long fun(long long b, long long p, long long k){
if(p == 1) return b % k;
return (fun(b, p / 2, k) % k * fun(b, p / 2, k) % k) % k;
}
为了处理当 p 出现奇数的情况，可在返回值处添加如下表达式：
(p % 2 == 0 ? 1 : b % k)
即当 p 为偶数时返回 1 ，否则返回 b % k
在 return 处，调用了 fun 函数两次，不妨优化一下
long long fun(long long b, long long p, long long k){
if(p == 1) return b % k;
int t = fun(b, p / 2, k) % k;
return (t * t * (p % 2 == 0 ? 1 : b % k)) % k;
}
看不懂呀
你没有记忆化
哦知道了谢谢
这就离谱
这样就好了
#include<bits/stdc++.h>
using namespace std;
long long x,y,z;
long long fz(long long a, long long b, long long c)
{
if(b==1) return a%c;
int t=fz(a,b/2,c)%c;
return (((t*t)%c)*(b%2==0?1:a%c))%c;
}
int main()
{
cin>>x>>y>>z;
cout<<x<<"^"<<y<<" mod "<<z<<"="<<fz(x,y,z);
return 0;
}
要多一个mod
别发代码
王泽通也发了呀
要不用用这个
不用了加个long long 就过了
你自己 int * int 不爆 int ？
他就是int
