牛客练习赛76 F-phi and phi 莫比乌斯反演+差分

• • 题意
  • 思路
  • Code(445MS)

传送门： https://ac.nowcoder.com/acm/contest/10845/F

题意

求 解 a n s [ i ] = ∑ i = 1 n ∑ j = 1 n φ ( i j ) φ [ g c d ( i , j ) ] 求解ans[i]=\sum_{i=1}^n\sum_{j=1}^n\varphi (ij)\varphi [gcd(i,j)] 求解ans[i]=i=1∑n​j=1∑n​φ(ij)φ[gcd(i,j)]

思路

前 置 技 能 ： φ ( i j ) = φ ( i ) φ ( j ) g c d ( i , j ) φ [ g c d ( i , j ) ] \red{前置技能：\varphi(ij)=\frac{\varphi(i) \varphi(j)gcd(i,j)}{\varphi[gcd(i,j)]}} 前置技能：φ(ij)=φ[gcd(i,j)]φ(i)φ(j)gcd(i,j)​

根 据 上 式 得 ： 根据上式得： 根据上式得：
∑ i = 1 n ∑ j = 1 n φ ( i ) φ ( j ) g c d ( i , j ) \sum_{i=1}^n\sum_{j=1}^n\varphi (i)\varphi(j)gcd(i,j) i=1∑n​j=1∑n​φ(i)φ(j)gcd(i,j)

∑ k = 1 n k ∑ i = 1 n ∑ j = 1 n φ ( i ) φ ( j ) [ g c d ( i , j ) = k ] \sum_{k=1}^nk\sum_{i=1}^n\sum_{j=1}^n\varphi (i)\varphi(j)[gcd(i,j)=k] k=1∑n​ki=1∑n​j=1∑n​φ(i)φ(j)[gcd(i,j)=k]

∑ k = 1 n k ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ n k ⌋ φ ( i k ) φ ( j k ) [ g c d ( i , j ) = 1 ] \sum_{k=1}^nk\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\varphi (ik)\varphi(jk)[gcd(i,j)=1] k=1∑n​ki=1∑⌊kn​⌋​j=1∑⌊kn​⌋​φ(ik)φ(jk)[gcd(i,j)=1]

∑ k = 1 n k ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ n k ⌋ φ ( i k ) φ ( j k ) ∑ d ∣ i    d ∣ j μ ( d ) \sum_{k=1}^nk\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\varphi (ik)\varphi(jk)\sum_{d|i\;d|j}\mu(d) k=1∑n​ki=1∑⌊kn​⌋​j=1∑⌊kn​⌋​φ(ik)φ(jk)d∣id∣j∑​μ(d)

交 换 枚 举 顺 序 ： 交换枚举顺序： 交换枚举顺序：

∑ k = 1 n k ∑ d = 1 ⌊ n k ⌋ μ ( d ) ∑ i = 1 ⌊ n k d ⌋ ∑ j = 1 ⌊ n k d ⌋ φ ( i k d ) φ ( j k d ) \sum_{k=1}^nk\sum_{d=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\mu(d)\sum_{i=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\varphi (ikd)\varphi(jkd) k=1∑n​kd=1∑⌊kn​⌋​μ(d)i=1∑⌊kdn​⌋​j=1∑⌊kdn​⌋​φ(ikd)φ(jkd)

∑ k = 1 n k ∑ d = 1 ⌊ n k ⌋ μ ( d ) [ ∑ j = 1 ⌊ n k d ⌋ φ ( i k d ) ] 2 \sum_{k=1}^nk\sum_{d=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\mu(d)[\sum_{j=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\varphi (ikd)]^2 k=1∑n​kd=1∑⌊kn​⌋​μ(d)[j=1∑⌊kdn​⌋​φ(ikd)]2

令 T = k d 并 交 换 枚 举 顺 序 ： 令T=kd并交换枚举顺序： 令T=kd并交换枚举顺序：

∑ T = 1 n ∑ k ∣ T k μ ( T k ) [ ∑ j = 1 ⌊ n T ⌋ φ ( i T ) ] 2 \sum_{T=1}^{n}\sum_{k|T}k\mu(\frac{T}{k})[\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT)]^2 T=1∑n​k∣T∑​kμ(kT​)[j=1∑⌊Tn​⌋​φ(iT)]2

由 φ = i d ∗ μ 得 ： 由\varphi = id*\mu得： 由φ=id∗μ得：

∑ T = 1 n φ ( T ) [ ∑ j = 1 ⌊ n T ⌋ φ ( i T ) ] 2 \sum_{T=1}^{n}\varphi(T)[\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT)]^2 T=1∑n​φ(T)[j=1∑⌊Tn​⌋​φ(iT)]2

设 f ( n / T ) = ∑ j = 1 ⌊ n T ⌋ φ ( i T ) ， 则 最 终 式 为 ： 设f(n/T)=\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT)，则最终式为： 设f(n/T)=∑j=1⌊Tn​⌋​φ(iT)，则最终式为：

a n s [ n ] = ∑ T = 1 n φ ( T ) [ f ( n / T ) ] 2 ans[n]=\sum_{T=1}^n\varphi(T)[f(n/T)]^2 ans[n]=T=1∑n​φ(T)[f(n/T)]2

但 是 这 题 要 求 的 是 a n s [ 1 − n ] ， 我 们 发 现 但是这题要求的是ans[1 - n]，我们发现 但是这题要求的是ans[1−n]，我们发现

在 枚 举 T 时 ， n 在 [ i ∗ T , ( i + 1 ) ∗ T ) 之 间 , n T 的 值 都 一 样 ， φ ( T ) [ f ( n / T ) ] 2 的 贡 献 不 变 。 在枚举T时，n在[i*T,(i+1)*T)之间,\frac{n}{T}的值都一样，\varphi(T)[f(n/T)]^2的贡献不变。 在枚举T时，n在[i∗T,(i+1)∗T)之间,Tn​的值都一样，φ(T)[f(n/T)]2的贡献不变。

所 以 我 们 在 求 a n s [ n ] 的 过 程 中 ， 对 i ∗ T 做 一 个 差 分 ， 最 后 在 求 一 个 前 缀 和 即 可 。 所以我们在求ans[n]的过程中，对i*T做一个差分，最后在求一个前缀和即可。 所以我们在求ans[n]的过程中，对i∗T做一个差分，最后在求一个前缀和即可。

Code(445MS)

#pragma GCC optimize(2)
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

#define INF 0x3f3f3f3f
#define lowbit(x) x & (-x)
#define mem(a, b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
 const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 1e6 + 10;

int vis[N * 3], prime[N * 3], num;
ll phi[N * 3], ans[N * 3];

void init() {
    phi[1] = 1; num = 0;
    for (int i = 2; i < N; i++) {
        if (!vis[i]) {
            prime[++num] = i; phi[i] = i - 1;
        }
        for (int j = 1; j <= num && i * prime[j] < N; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
}

void solve() {
    init();
    int n; scanf("%d",&n);
    for(int T = 1;T <= n; T++) {
        ll sum = 0;
        for(int i = 1;i <= n / T; i++) {
            sum = (sum + phi[i * T]) % mod;
            ans[i * T] = (ans[i * T] + phi[T] * sum % mod * sum % mod + mod) % mod;
            ans[(i + 1) * T] = (ans[(i + 1) * T] - phi[T] * sum % mod * sum % mod + mod) % mod;
        }
    }
    for(int i = 1;i <= n; i++) {
        ans[i] = ((ans[i] + ans[i - 1]) % mod + mod) % mod;
        printf("%lld\n",ans[i]);
    }
    // cout << endl;
}

signed main() {
    solve();
}