HDU1452:Happy 2004（积性函数）（因子和）

题意

给出$x$，求$2004^x$的所有因子和

分析

$2004=2*2*3*167$

则$2004^x$=$2^{2x}*3^x*167^x$

s[$2004^x$]=s[$2^{2x}$]s[$3^x$]s[$167^x$]

s[i]为积性函数

如果$p$为素数，则$s(p^x) = (1 + p^1 + p^2 + ... p^x) = (p^{x+1} - 1) / (p-1) $

然后求出2，3，167的逆元即可

注意开long long

代码

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <ctime>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <bitset>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#define cpy(a,b) memcpy(a,b,sizeof(b))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int a[4]={0,2,3,22},x;

const int mod=29;

ll work(int p,int x)

{

    ll ret=1;

    for(;x;x>>=1,(p*=p)%=mod) if(x&1) (ret*=p)%=mod;

    return ret;

}

int main()

{

    while(scanf("%d",&x),x)

    {

        ll ans=1;ans=ans*(work(a[1],2*x+1)-1)%mod;

        F(i,2,3)

        ans=ans*((work(a[i]%mod,x+1)-1)*work((a[i]-1)%mod,mod-2))%mod;

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

HDU1452:Happy 2004（积性函数）（因子和）

最新文章

热门文章