ACM_同余+暴力找规律

Problem Description:

锴神：我尊重作者原意，你们出什么我就加什么。于是小光打了道水题（也就是这道），但是呢比赛的时候拿着自己的标程却AC不了，最后只能尴尬地打表！！为毛呢？！请你来看看这道题，为了缓解小光的尴尬，他决定不告诉你样例输入输出，神马？！没有输入输出？对，就是这么贼！

Input:

多组数据，输入n,求(1^n+2^n+3^n+4^n)mod 5,其中n范围是[10^5,10^(10^5)]，数字可能有前导0。

Output:

当然是结果啦~

Sample Input:

不给你

Sample Output:

就是不给你
解题思路：题目的意思很简单，已经提示要找规律，于是（快速幂）暴力枚举查找，发现如果是4的倍数，计算结果是4，否则为0。其中红色部分n的区间数的位数是5位数到10万位数，因此字符串长度开10^5+5即可。注意读取的字符串可能前导有0，所以要去掉前导的'0'。
测试代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 LL mod_pow(LL base,LL n,LL mod){//快速幂

     LL res=;

     while(n){

         if(n&)res=res*base%mod;

         base=base*base%mod;

         n>>=;

     }

     return res;

 }

 int main(){

     LL sum=;//测试

     for(int i=;i<;++i){

         sum=(mod_pow(,i,)+mod_pow(,i,)+mod_pow(,i,)+)%;

         cout<<i<<' '<<sum<<endl;

         if(i%==)cout<<i<<"是可以的"<<endl;

     }

     return ;

 }

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 char s[];

 int main(){

     while(cin>>s){

         int sum=,j=;

         while(s[j]=='')++j;//去掉前导0

         for(int i=j;i<(int)strlen(s);++i)

             sum=(sum*+(s[i]-'')%)%;//同余方程

         if(sum)cout<<''<<endl;//如果sum不是0则结果为0，否则为4

         else cout<<''<<endl;

     }

     return ;

 }

 同余定理的还有：hdu 1212 Big Number

巴特西

ACM_同余+暴力找规律

Problem Description:

Input:

Output:

Sample Input:

Sample Output:

最新文章

热门文章