重庆有没有做网站的,绍兴网站设计公司,网站关键词,静态网站 动态#6229. 这是一道简单的数学题
推式子 ∑i1n∑j1ilcm(i,j)gcd(i,j)(∑i1n∑j1nlcm(i,j)gcd(i,j)n)∗inv2所以重点求∑i1n∑j1nlcm(i,j)gcd(i,j)∑i1n∑j1nijgcd(i,j)2∑d1n∑i1nd∑j1ndij(gcd(i,j)1)∑d1n∑k1ndμ(k)k2(∑i1nkdi)2我们另tkd#xff0c;得到∑t1n(∑i1nti)2∑k…#6229. 这是一道简单的数学题
推式子
∑i1n∑j1ilcm(i,j)gcd(i,j)(∑i1n∑j1nlcm(i,j)gcd(i,j)n)∗inv2所以重点求∑i1n∑j1nlcm(i,j)gcd(i,j)∑i1n∑j1nijgcd(i,j)2∑d1n∑i1nd∑j1ndij(gcd(i,j)1)∑d1n∑k1ndμ(k)k2(∑i1nkdi)2我们另tkd得到∑t1n(∑i1nti)2∑k∣tμ(k)k2接下来就是考虑如何在非线性的时间内筛选出∑k∣tμ(k)k2的前缀和来我们设f(n)(μid2∗I)(n)也就是∑k∣tμ(k)k2的卷积形式。g(n)id2,显然有f(n)∗g(n)μid2∗I∗id2μid2∗id2∑d∣nμ(d)d2(nd)2n2ϵϵ所以有f(n)∗g(n)I套进杜教筛里面去得到S(n)∑i1nI−∑d2nd2S(nd)\sum_{i 1} ^{n} \sum_{j 1} ^{i} \frac{lcm(i, j)}{gcd(i, j)}\\ (\sum_{i 1} ^{n} \sum_{j 1} ^{n} \frac{lcm(i, j)}{gcd(i, j)} n) * inv2\\ 所以重点求\sum_{i 1} ^{n} \sum_{j 1} ^{n} \frac{lcm(i, j)}{gcd(i, j)}\\ \sum_{i 1} ^{n} \sum_{j 1} ^{n} \frac{ij}{gcd(i, j) ^ 2}\\ \sum_{d 1} ^{n} \sum_{i 1} ^{\frac{n}{d}} \sum_{j 1} ^{\frac{n}{d}}ij (gcd(i, j) 1)\\ \sum_{d 1} ^{n} \sum_{k 1} ^{\frac{n}{d}} \mu(k) k ^ 2 (\sum_{i 1} ^{\frac{n}{kd}} i) ^ 2\\ 我们另t kd得到\\ \sum_{t 1} ^{n} (\sum_{i 1} ^{\frac{n}{t}}i) ^ 2 \sum_{k \mid t} \mu(k) k ^ 2\\ 接下来就是考虑如何在非线性的时间内筛选出\sum_{k \mid t} \mu(k) k ^ 2的前缀和来\\ 我们设f(n) (\mu\ id ^ 2 * I)(n)也就是\sum_{k \mid t} \mu(k) k ^ 2的卷积形式。\\ g(n) id ^ 2, 显然有f(n) * g(n) \mu\ id ^ 2 * I * id ^ 2\\ \mu\ id ^ 2 * id ^ 2 \sum_{d \mid n} \mu(d) d ^ 2 (\frac{n}{d}) ^ 2 n ^ 2\epsilon \epsilon\\ 所以有f(n) * g(n) I\\ 套进杜教筛里面去得到S(n) \sum_{i 1} ^{n} I - \sum_{d 2} ^{n} d ^ 2S(\frac{n}{d})\\ i1∑nj1∑igcd(i,j)lcm(i,j)(i1∑nj1∑ngcd(i,j)lcm(i,j)n)∗inv2所以重点求i1∑nj1∑ngcd(i,j)lcm(i,j)i1∑nj1∑ngcd(i,j)2ijd1∑ni1∑dnj1∑dnij(gcd(i,j)1)d1∑nk1∑dnμ(k)k2(i1∑kdni)2我们另tkd得到t1∑n(i1∑tni)2k∣t∑μ(k)k2接下来就是考虑如何在非线性的时间内筛选出k∣t∑μ(k)k2的前缀和来我们设f(n)(μ id2∗I)(n)也就是k∣t∑μ(k)k2的卷积形式。g(n)id2,显然有f(n)∗g(n)μ id2∗I∗id2μ id2∗id2d∣n∑μ(d)d2(dn)2n2ϵϵ所以有f(n)∗g(n)I套进杜教筛里面去得到S(n)i1∑nI−d2∑nd2S(dn)
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h
#define endl \nusing namespace std;typedef long long ll;const int inf 0x3f3f3f3f;
const double eps 1e-7;const int mod 1e9 7, N 1e6 10, inv6 166666668, inv2 500000004;int prime[N], mu[N], cnt;ll sum[N];bool st[N];ll quick_pow(ll a, int n) {ll ans 1;while(n) {if(n 1) ans ans * a % mod;a a * a % mod;n 1;}return ans;
}void init() {mu[1] 1;for(int i 2; i N; i) {if(!st[i]) {prime[cnt] i;mu[i] -1;}for(int j 0; j cnt i * prime[j] N; j) {st[i * prime[j]] 1;if(i % prime[j] 0) break;mu[i * prime[j]] -mu[i];}}for(int i 1; i N; i) {for(int j i; j N; j i) {sum[j] (sum[j] 1ll * i * i % mod * mu[i] % mod mod) % mod;}}for(int i 1; i N; i) {sum[i] (sum[i] sum[i - 1]) % mod;}
}ll calc1(ll n) {ll ans 1ll * (1 n) * n / 2 % mod;return 1ll * ans * ans % mod;
}ll calc2(ll n) {return 1ll * n * (n 1) % mod * (2 * n 1) % mod * inv6 % mod;
}unordered_mapint, int ans_s;ll S(int n) {if(n N) return sum[n];if(ans_s.count(n)) return ans_s[n];ll ans n;for(ll l 2, r; l n; l r 1) {r n / (n / l);ans (ans - 1ll * (calc2(r) - calc2(l - 1) mod) % mod * S(n / l) % mod mod) % mod;}return ans_s[n] ans;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);// cout quick_pow(2, mod - 2) endl;init();ll n, ans 0;scanf(%lld, n);for(ll l 1, r; l n; l r 1) {r n / (n / l);ans (ans 1ll * calc1(n / l) * ((S(r) - S(l - 1) mod) % mod) % mod) % mod;}printf(%lld\n, 1ll * (ans n) * inv2 % mod);return 0;
}
