[Project Euler 429] Sum of squares of unitary divisors（数论）

题目链接：https://projecteuler.net/problem=429

题目：

我们称 N 的约数 d 为特殊的当且仅当 gcd(d, n / d) = 1.

设 S(n) 为 n 所有特殊的约数的平方和. 现在给定 N, 求 S(N!) 模 1e7 + 9.

题解：

第二行的"所以 S(n²) "改成"所以 S(n!)"

代码如下：

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;

const int N=1e8+15;
const int mod=1e9+9;
ll n,tot,ans;
ll prime[N],vis[N];
void get_prime()
{
    for (ll i=2;i<=n;i++)
    {
        if (!vis[i]) prime[++tot]=i;
        for (ll j=1;j<=tot&&prime[j]*i<=n;j++)
        {
            vis[prime[j]*i]=1;
            if (i%prime[j]==0) break;
        }
    }
}
ll mul(ll a,ll b)
{
    ll res=0;
    for (;b;b>>=1,a=(a+a)%mod) if (b&1) res=(res+a)%mod;
    return res;
}
ll qpow(ll a,ll b)
{
    ll res=1;
    for (;b;b>>=1,a=mul(a,a)%mod) if (b&1) res=res*a%mod;
    return res;
}
ll solve(ll a,ll b)
{
    ll res=0;
    while (a)
    {
        a/=b;
        res+=a;
    }
    return res;
}
int main()
{
    //scanf("%lld",&n);
    n=1e8;
    ans=1;
    get_prime();
    for (ll i=2;i<=n;i++)
    {
        if (!vis[i])
        {
            ll power=solve(n,i);
            ans=1ll*ans*(qpow(i,power*2)+1)%mod;
        }
    }
    printf("%lld",ans);
    return 0;
}

本博客内容转自http://www.cnblogs.com/LzyRapx/p/8280943.html