tips:
1.(a*b)%c=[(a%c)*(b%c)]%c, 其他的公式都是由此引出的
2. 代码里主要是这样处理了 (a*b)%c=(a%c)*b%c
3. 快速幂也叫二分幂, 有递归写法, 判断 b 的奇偶, 详见算法笔记
- //long long 如果输入不使用 %lld 的话, 如果输入数据超过 int 范围会 wa
- //(a+b)%c=(a%c b%c)%c;
- //(a*b)%c=[(a%c)*(b%c)]%c
- //(a^b)%c=(a%c)^b%c--- 幂是多次乘法
- //(a*b)%c=(a%c)*b%c
- // 有详细证明: https://blog.csdn.net/qq_36285879/article/details/53284431
- #include<cstdio>
- using namespace std;
- int z;
- int m,h;
- long long ans,a,b;
- long long binaryPow(long long a,long long b, int m ){
- long long ans=1;
- while(b>0){
- if(b&1){
- ans=ans*a%m;//(a*b)%c=(a%c)*b%c
- }
- a=a*a%m;//(a%c)
- b=b>>1;
- }
- return ans;
- }
- int main(){
- scanf("%d",&z);
- while(z--){
- scanf("%d%d",&m,&h);
- long long ans=0;
- for(int i=0;i<h;i++){
- scanf("%lld%lld",&a,&b);
- ans+=binaryPow(a,b,m);
- }
- ans=ans%m;
- printf("%lld\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2728503.html