Project Euler 531

发表于 更新于 分类于 阅读次数： 本文字数： 522 阅读时长 ≈ 1 分钟

Project Euler 531

题目

Chinese leftovers

Let $g(a,n,b,m)$ be the smallest non-negative solution $x$ to the system:

$\begin{aligned}
& x = a \bmod n\
& x = b \bmod m
\end{aligned}$

if such a solution exists, otherwise $0$.

E.g. $g(2,4,4,6)=10$, but $g(3,4,4,6)=0$.

Let $\varphi(n)$ be Euler’s totient function.

Let $f(n,m)=g(\varphi(n),n,\varphi(m),m)$.

Find $\sum f(n,m)$ for $1000000 \le n < m < 1005000$.

解决方案

题意比较裸，直接求出欧拉函数值然后通过中国剩余定理求方程的解即可。

当然也可以令$x=t_an+a=t_bm+b$，那么可以写出方程$t_an-t_bm=b-a$，只需要用一次扩展欧几里得算法就可以求出$t_a,t_b$，从而重新计算出$x$。这种做法比起使用中国剩余定理，少使用了一次扩展欧几里得算法，故也可以考虑。

代码

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
39
40
41
42
43
44
45
46
47
48
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int L=1000000,R=1005000;
int phi[R+4];
ll ex_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;return a;
    }
    ll g=ex_gcd(b,a%b,x,y);
    ll z=x-(a/b)*y;
    x=y;y=z;return g;
}
//解不定方程ax+my=c。
ll congruence(ll a,ll c,ll m){
    ll x,y,g;
    g=ex_gcd(a,m,x,y);
    if(c%g!=0) return -1;
    x*=c/g;
    ll t=m/g;
    return (x%t+t)%t;
}
ll CRT(ll b,ll m,ll c,ll n){
    ll y=congruence(m,c-b,n);
    if(y==-1) return -1;
    ll x=m*y+b;
    ll t=m*n;
    return (x%t+t)%t;
}
int main(){
    for(int i=1;i<R;i++)
        phi[i]=i;
    for(int i=2;i<R;i++){
        if(phi[i]!=i) continue;
        phi[i]=i-1;
        for(int j=i+i;j<R;j+=i)
            phi[j]=phi[j]/i*(i-1);
    }
    ll ans=0;
    for(int i=L;i<R;i++){
        for(int j=i+1;j<R;j++){
            ll x=CRT(phi[i],i,phi[j],j);
            if(x!=-1) ans+=x;
        }
    }
    printf("%lld\n",ans);
}