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

【HDU6706|HDU6706 huntian oy(2019年CCPC网络赛+杜教筛)】目录

题目链接
思路
代码

题目链接传送门
思路看到这题还比较懵逼，然后机房大佬板子里面刚好有这个公式\(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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; typedef pair pLL; typedef pair pLi; typedef pair pil; ; typedef pair 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"=["< 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; }