暑假第1次个人赛I题 求(a^b)%c、
(这是一个解决b在long long 范围内的方法 可以算1个模板吧,本次题 范围是10^100 听师姐说的非常之麻烦 正在努力研究中 这种方法姑且放着以后用咯  可过fzu 1752)

用了两种算法
1:
求(a^b)%c=(a%c^b%c)%c
因为测试数据过大 (a%c^b%c)可能溢出 所以采用2分法 转换为加法求余搞定
2:
求(a^b)
用FOR 循环 如果b是奇数 总和s*=a b–;偶数 a=a*a b/=2 具体优化时间
如果大神们还有优化方法 望告知哦~
#include<stdio.h>
#include<math.h>
long long int fen(long long int a,long long int b,long long int c)
{
 long long int x=0;
 while(b)
 {
  if (b&1)
  {
   x+=a;
   if(x>=c)
    x-=c;
  }
  a<<=1;
  if(a>=c)
   a-=c;
  b>>=1;
 }
 return x;
}

long long int suan(long long int a,long long int b,long long int c)
{
    long long int s=1;
 while(b)
    {
        if(b%2==1)
        {
            s=fen(s,a,c);
        }
        a=fen(a,a,c);
  b=b>>1;
    }
    return s;
}

int main()
{
 long long int a,b,c;
 while(scanf("%lld %lld %lld",&a,&b,&c)!=EOF)
 {
 printf("%lld\n",suan(a,b,c)%c);
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation