UOJ Logo insilent的博客

博客

#115. 幻想乡的烤红薯队伍比较坚强

2018-03-14 18:29:20 By insilent

事实证明暴力一个点都过不了


本题主要求和(以及快速幂)

当k为偶数时:

比如 k=6,那么 A+A^2+A^3+A^4+A^5+A^6=A+A^2+A^3+ A^3*(A+A^2+A^3)

s(k)=s(k/2)+A^(n/2) s(k/2)=s(k/2)\(1+A^(n/2))

当k为奇数时:

s(k)=s(k-1)+A^k , 那么k-1为偶数,可以按照上面的二分


再加上取模的基本运算:

(a*b)%m=((a%m)*(b%m))%m

(a+b)%m=((a%m)+(b%m))%m


上代码

#include<bits/stdc++.h>
using namespace std;
//(a*b)%c=((a%c)*(b%c))%c
int m;
long long power(long long n,long long b)        //快速幂
{
    if(b==1)
        return n%m;
    long long ans=power(n,b/2);
    ans=(ans*ans)%m;
    if(b%2==1)
        ans=(ans*(n%m))%m;
    return ans;
}
long long Mod(long long n,long long k)
{
    if(k==1)
        return n%m;
    if(k&1)
    {
        return (Mod(n,k-1)+power(n,k))%m;        //当k为奇数时,减1变为偶数 S(K)=S(K-1)+A^K  
    }
    else
    {
        return (((1+power(n,k>>1)))%m*Mod(n,k>>1))%m;        //当K为偶数时,S(K)=(1+A^(K/2))*S(K/2)  
    }
}
int main()
{
    long long n,k;
    cin>>n>>k>>m;
    printf("%lld",Mod(n,k));
    return 0;
}

评论

luv_letters
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。