A simple Blog for wyx I've been down the bottle hoping.
4804: 欧拉心算 数论 欧拉函数
发表于: | 分类: Oi | 评论:0 | 阅读:52

省选上午的时候推得式子推出一坨反演然后不会写慌的yibi现在一看和反演一点关系都没有2333333

$\sum_{i=1}^n\sum_{j=1}^n {\phi(\gcd(i,j))}$

$\sum_{d=1}^n\phi(d)\sum_{i=1}^n\sum_{j=1}^n{\gcd(i,j)==d}$

$\sum_{d=1}^n \phi(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}} {\gcd(i,j) == 1}$

我们先强制让后面的循环$j \le i$这样的话显然前一半的答案就是$\phi(\frac{n}{d})$

整体相当于一个$n\times n$的对称数表知道一半求另一半显然*2即可

所以大力分块即可

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e7+5;
const int Max = 1e7;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int prime[N], cnt;
LL phi[N];
bool F[N];

inline void init() {
    phi[1] = 1;
    register int j;
    int temp;
    for(int i=2;i<=Max;++i) {
        if(!F[i]) {
            prime[++cnt] = i;
            phi[i] = i-1;
        }
        for(j=1;prime[j]*i<=Max;++j) {
            F[temp = (i*prime[j])] = true;
            if(i%prime[j]==0) {
                phi[temp] = phi[i] * prime[j];
                break;
            }
            phi[temp] = phi[i] * (prime[j]-1);
        }
    }
    for(int i=2;i<=Max;++i) phi[i] += phi[i-1];
}

int main() {
    init();
    int T = read(), n ;
    LL ans;
    while(T--) {
        n = read();
        ans = 0;
        for(int i=1,last=0;i<=n;i=last+1) {
            last = n/(n/i);
            ans += (phi[last]-phi[i-1])*(phi[n/i]*2-1);
        }
        printf("%lld\n", ans);
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP