Project Euler 429

Project Euler 429

题目

Sum of squares of unitary divisors

A unitary divisor d of a number n is a divisor of n that has the property gcd(d,nd)=1.

The unitary divisors of 4!=24 are 1,3,8 and 24.

The sum of their squares is 12+32+82+242=650.

Let S(n) represent the sum of the squares of the unitary divisors of n. Thus S(4!)=650.

Find S(100000000!) modulo 1000000009.

解决方案

如果一个正整数 n 分解后成为:

n=i=1mpiei

对于 n 的某个因子 d=i=1mpiei 而言,如果 gcd(d,nd)=1,那么对于所有 i[1,m],都有 ei0,ei

原因:如果 d 的一个质因子 pi 的指数 ei{0,ei},也就是 0<ei<ei,那么 nd 对应下的质因子的指数为 0<eiei<ei,因此 gcd(d,nd) 一定是 pi 的倍数,所以原来的命题成立。

这些因子一共有 2m 个,因为对于所有 i[1,m]ei 都有两个选择。因此,这 2m 个因子的平方和为:

S(n)=i=1m(pi2ei+1)

另一个问题则是:n! 中质因子 p 出现了多少次?

f(n,p) 是质因子 p n! 中的次数,那么 f(n,p)=np+np2+np3+,每一项分别表示 1n 中有多少个数是 p,p2,p3 的倍数。

最终,将这 2 个过程相结合,直接计算 S(N!) 的值,其中 N=108

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e8;
ll mod=1e9+9;
ll qpow(ll n,ll m){
ll ans=1;
for(;m;m>>=1){
if(m&1) ans=ans*n%mod;
n=n*n%mod;
}
return ans;
}
int cal(int n,int p){
int ans=0;
for(;n;n/=p)
ans+=n/p;
return ans;
}
int pr[N+4],v[N+4],m=0;
int main(){
for(int i=2;i<=N;i++){
if(v[i]==0){
v[i]=i;pr[++m]=i;
}
for(int j=1;j<=m;j++){
if(pr[j]>v[i]||pr[j]>N/i) break;
v[i*pr[j]]=pr[j];
}
}
ll ans=1;
for(int i=1;i<=m;i++){
ll cnt=cal(N,pr[i]);
ans=ans*(qpow(pr[i],cnt*2)+1)%mod;
}
printf("%lld\n",ans);
}

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝