HDU1452:Happy 2004(求因子和+分解质因子+逆元）上一题的简单版

题目链接：传送门

题目要求：求S(2004^x)%29。

题目解析：因子和函数为乘性函数，所以首先质因子分解s(2004^x)=s(2^2*x)*s(3^x)*s(167^x);

因为2与29，166与29互质，所以都存在逆元，直接解就可以。刚开始做的时候这题困扰了我很长时间。

这是我之前没怎么看懂的原因：同余性质：若 a=b(mod m) 则 a^k=b^k (mod m)：
所以 167可以用 22代替，（对29 同余）

167%29==22%29

169^x%29==22^x%29

而为什么s(167^x)%29=(167^x+1 -1）/166%mod=(((167%29)^x+1 -1)%mod/(166%mod))%mod=(22^x+1 -1)/21%mod，但是我不怎么懂，他们为什么直接

根据s(167^x)%mod==s(22^x)%mod,现在貌似懂了。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#define mod 29

using namespace std;

typedef long long ll;

ll mpow(ll x,ll k)

{

    ll t=;

    while(k)

    {

        if(k&) t=((t%mod)*(x%mod))%mod;

        k>>=;

        x=((x%mod)*(x%mod))%mod;

    }

    return t;

}

ll X,Y;

void extend(ll A,ll B,ll &x1,ll &y1)

{

    if(B==)

    {

       x1=;

       y1=;

       return ;

    }

    extend(B,A%B,x1,y1);

     ll t=x1;

     x1=y1;

     y1=t-(A/B)*y1;

}

int main()

{

    int n;

    ll a,b,c,sum,temp;

    while(scanf("%d",&n)!=EOF&&n!=)

    {

        sum=;

        temp=*n+;

        a=mpow(,temp);

        a=(a-)%mod;

        b=mpow(,n+);

        b=(b-)%mod;

        b=(b*)%mod;

        c=mpow(,n+);

        c=(c-)%mod;

        extend(,,X,Y);

        X=(X%mod+mod)%mod;

        c=(c*X)%mod;

        sum=((a%mod)*(b%mod)*(c%mod))%mod;

        printf("%I64d\n",sum);

    }

    return ;

}

巴特西

HDU1452:Happy 2004(求因子和+分解质因子+逆元）上一题的简单版

最新文章

热门文章