UVA - 11426 GCD - Extreme (II)

傳送門UVA - 11426

題意

給你 n n ，讓你求

∑i=1n−1∑j=i+1ngcd(i,j)∑i=1n−1∑j=i+1ngcd(i,j)

題解

這道題就是個篩法的經典練習。

首先，設一個函數 f(x) f ( x )

f(x)=∑i=1x−1∑j=i+1xgcd(i,j) f ( x ) = ∑ i = 1 x − 1 ∑ j = i + 1 x g c d ( i , j )

那麼我們可以再設一個函數 g(x) g ( x )

g(x)=∑i=1x−1gcd(i,x) g ( x ) = ∑ i = 1 x − 1 g c d ( i , x )

那麼很顯然

f(x)=f(x−1)+g(x) f ( x ) = f ( x − 1 ) + g ( x )

那麼我們就得到了一個遞推式，這時我們就要想怎麼得到所有的 g(x) g ( x )

那我們再設一個 h(n,x) h ( n , x )

h(n,x)=countni=1(gcd(n,i)=x)(ps:count是指求個數) h ( n , x ) = c o u n t i = 1 n ( g c d ( n , i ) = x ) ( p s : c o u n t 是 指 求 個 數 )

那麼顯然

g(x)=∑i=1n(h(x,i)×i) g ( x ) = ∑ i = 1 n ( h ( x , i ) × i )

然後我們又知道

gcd(n,i)=x g c d ( n , i ) = x

⇒gcd(nx,ix)=1 ⇒ g c d ( n x , i x ) = 1

那麼

countni=1(gcd(nx,ix)=1)=phi(nx)(phi為歐拉函數) c o u n t i = 1 n ( g c d ( n x , i x ) = 1 ) = p h i ( n x ) ( p h i 為 歐 拉 函 數 )

那麼我們就要預處理出來所有數字的歐拉函數，然後再用篩法求出所有的 g(x) g ( x ) ,然後再推出 f(x) f ( x )

首先數字挺大的了，先寫一個 O(n) O ( n ) 的歐拉篩

ll phi[maxn];
bool notp[maxn];
ll prime[maxn], tot;

void getphi(int M) {
    phi[] = ;
    for (int i = ; i <= M; i++) {
        if (!notp[i]) {
            prime[++tot] = i;
            phi[i] = i - ;
        }
        for (int j = ; j <= tot && i * prime[j] <= M; j++) {
            notp[i * prime[j]] = true;
            if (i % prime[j] == ) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - );
        }
    }
}
           

實際上我們隻要求出了歐拉函數就不用求 h(n,x) h ( n , x ) 了，直接篩出 g(x) g ( x ) 就行

for (int i = ; i < maxn; ++i) {
    for (int j = i * ; j < maxn; j += i) {
        g[j] += phi[j / i] * i;
    }
}
           

剩下就沒有難點了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <iomanip>
//#include <unordered_map>

#pragma comment(linker, "/STACK:102400000,102400000")
#define fir first
#define sec second
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define clr(x) memset(x,0,sizeof(x))
#define cld(x) memset(x,-1,sizeof(x))
#define clx(x) memset(x,63,sizeof(x))
#define cln(x) memset(x,-64,sizeof(x))
#define rush() int T;scanf("%d",&T);for(int NUM = 1; NUM <= T ; ++NUM)
#define pi 3.1415926
#define VM 100047
#define EM 400047
#define rd(x) scanf("%d",&x);
#define seed() srand((unsigned)time(NULL))
#define random(a, b) rand() % (b - a + 1) + a
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int inf = ;
const ll llf = ;
const int maxn = (int)  + ;
const double eps = ;
const ll mod1 = (int)  + ;
const ll mod2 = ;
const ll has = ;
const int dx[] = {, , , -};
const int dy[] = {, , -, };
ll phi[maxn];
bool notp[maxn];
ll prime[maxn], tot;

void getphi(int M) {
    phi[] = ;
    for (int i = ; i <= M; i++) {
        if (!notp[i]) {
            prime[++tot] = i;
            phi[i] = i - ;
        }
        for (int j = ; j <= tot && i * prime[j] <= M; j++) {
            notp[i * prime[j]] = true;
            if (i % prime[j] == ) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - );
        }
    }
}

ll g[maxn], f[maxn];

int main() {
    std::ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    clr(notp);
    getphi(maxn - );
    ll n;
    for (int i = ; i < maxn; ++i) {
        for (int j = i * ; j < maxn; j += i) {
            g[j] += phi[j / i] * i;
        }
    }
    for (int i = ; i < maxn; ++i) {
        f[i] = f[i - ] + g[i];
    }
    while (~scanf("%lld", &n) && n) {
        printf("%lld\n",f[n]);
    }


    return ;
}