题目链接

思路

看到这题还比较懵逼，然后机房大佬板子里面刚好有这个公式\(gcd(a^n-b^n,a^m-b^m)=a^{gcd(n,m)}-b^{gcd(n,m)}\)，然后自己随手推了一下就过了。

在知道上面那个公式后化简如下：

\[\begin{aligned}
&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}(i-j)[gcd(i,j)=1]&\\
=&\sum\limits_{i=1}^{n}(i\phi(i)-\sum\limits_{j=1}^{i}j[gcd(i,j)=1]&\\
=&\sum\limits_{i=1}^{n}i\phi(i)-\frac{i\phi(i)}{2}&\\
=&\frac{1}{2}(\sum\limits_{i=1}^{n}i\phi(i)-1)&
\end{aligned}
\]

第一步到第二步是算\(i\)的贡献，第二步到第三步是小于\(i\)且与\(i\)互质的数的和。

然后我们可以用杜教筛来求解这个东西，杜教筛推导过程可以看这篇博客。

代码

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cassert>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson (rt<<1),L,mid

#define rson (rt<<1|1),mid + 1,R

#define lowbit(x) x&(-x)

#define name2str(name) (#name)

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl

#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)

#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;

const int mod = 1000000007;

const int maxn = 3000000 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

bool v[maxn];

int phi[maxn], p[maxn];

int t, n, a, b, cnt, inv, inv2;

LL sum[maxn];

unordered_map<int, LL> dp;

LL qpow(LL x, int n) {

    LL res = 1;

    while(n) {

        if(n & 1) res = res * x % mod;

        x = x * x % mod;

        n >>= 1;

    }

    return res;

}

void init() {

    phi[1] = 1;

    for(int i = 2; i < maxn; ++i) {

        if(!v[i]) {

            p[cnt++] = i;

            phi[i] = i - 1;

        }

        for(int j = 0; j < cnt && i * p[j] < maxn; ++j) {

            v[i*p[j]] = 1;

            if(i % p[j] == 0) {

                phi[i*p[j]] = phi[i] * p[j];

                break;

            }

            phi[i*p[j]] = phi[i] * (p[j] - 1);

        }

    }

    for(int i = 1; i < maxn; ++i) sum[i] = (sum[i-1] + 1LL * i * phi[i] % mod) % mod;

}

LL dfs(int x) {

    if(x < maxn) return sum[x];

    if(dp.count(x)) return dp[x];

    LL ans = 1LL * x * (x + 1) % mod * (2LL * x % mod + 1) % mod * inv % mod;

    for(int l = 2, r; l <= x; l = r + 1) {

        r = x / (x / l);

        LL tmp = 1LL * (r - l + 1) * (l + r) / 2;

        tmp %= mod;

        ans = ((ans - 1LL * tmp % mod * dfs(x / l) % mod) % mod + mod) % mod;

    }

    return dp[x] = ans;

}

int main() {

#ifndef ONLINE_JUDGE

    FIN;

#endif

    init();

    inv = qpow(6, mod - 2);

    inv2 = qpow(2, mod - 2);

    scanf("%d", &t);

    while(t--) {

        scanf("%d%d%d", &n, &a, &b);

        LL tmp = dfs(n);

        printf("%lld\n", (dfs(n) - 1 + mod) % mod * inv2 % mod);

    }

    return 0;

}

巴特西

HDU6706 huntian oy(2019年CCPC网络赛+杜教筛)

题目链接

思路

代码

最新文章

热门文章