当前位置:网站首页>P1390 sum of common divisor (Mobius inversion)
P1390 sum of common divisor (Mobius inversion)
2022-04-23 09:42:00 【Zimba_】
The question :
Given n n n, seek ∑ i = 1 n ∑ j = i + 1 n g c d ( i , j ) \sum_{i=1}^{n}\sum_{j=i+1}^{n}gcd(i,j) ∑i=1n∑j=i+1ngcd(i,j). ( n < = 2 e 6 ) (n<=2e6) (n<=2e6)
deduction :
First step , Follow the routine first g c d gcd gcd Bring it to the front ,
∑ g = 1 n g ∑ i = 1 n ∑ j = i + 1 n [ g = g c d ( i , j ) ] \sum_{g=1}^{n}g\sum_{i=1}^{n}\sum_{j=i+1}^{n}[g=gcd(i,j)] ∑g=1ng∑i=1n∑j=i+1n[g=gcd(i,j)]
The second step , We make f ( g ) = ∑ i = 1 n ∑ j = i + 1 n [ g = g c d ( i , j ) ] f(g)=\sum_{i=1}^{n}\sum_{j=i+1}^{n}[g=gcd(i,j)] f(g)=∑i=1n∑j=i+1n[g=gcd(i,j)], What we ask for at this time is ∑ g = 1 n g f ( g ) \sum_{g=1}^{n}gf(g) ∑g=1ngf(g), Put it first. .
Then at this time, we choose one from the formula of Mobius inversion , Once you have experience, you will know which one to choose .
We make ,
F ( g ) = ∑ g ∣ d f ( d ) F(g)=\sum_{g|d}f(d) F(g)=∑g∣df(d)
= ∑ g ∣ d ∑ i = 1 n ∑ j = i + 1 n [ d = g c d ( i , j ) ] \;\;\;\;\;\;\;\;=\sum_{g|d}\sum_{i=1}^{n}\sum_{j=i+1}^{n}[d=gcd(i,j)] =∑g∣d∑i=1n∑j=i+1n[d=gcd(i,j)]
= ∑ i = 1 n ∑ j = i + 1 n [ g ∣ g c d ( i , j ) ] \;\;\;\;\;\;\;\;=\sum_{i=1}^{n}\sum_{j=i+1}^{n}[g|gcd(i,j)] =∑i=1n∑j=i+1n[g∣gcd(i,j)]
= ∑ i = 1 n ∑ j = i + 1 n [ g ∣ i ∧ g ∣ j ] \;\;\;\;\;\;\;\;=\sum_{i=1}^{n}\sum_{j=i+1}^{n}[g|i\wedge g|j] =∑i=1n∑j=i+1n[g∣i∧g∣j]
= 1 2 ( ⌊ n g ⌋ ⌊ n g ⌋ − ⌊ n g ⌋ ) \;\;\;\;\;\;\;\;=\frac{1}{2} (\lfloor \frac{n}{g} \rfloor \lfloor \frac{n}{g} \rfloor -\lfloor \frac{n}{g} \rfloor) =21(⌊gn⌋⌊gn⌋−⌊gn⌋)
According to the inversion formula , Yes f ( g ) = ∑ g ∣ d μ ( d g ) F ( d ) f(g)=\sum_{g|d}\mu(\frac{d}{g})F(d) f(g)=∑g∣dμ(gd)F(d)
So let's go back to the original formula ,
∑ g = 1 n g f ( g ) = ∑ g n ∑ g ∣ d μ ( d g ) F ( d ) \sum_{g=1}^{n}gf(g)=\sum_{g}^{n}\sum_{g|d}\mu(\frac{d}{g})F(d) ∑g=1ngf(g)=∑gn∑g∣dμ(gd)F(d)
Pushed ahead , F ( d ) F(d) F(d) Sure o ( 1 ) o(1) o(1) count , Mobius function can preprocess , So the final formula can o ( n l o g n ) o(nlogn) o(nlogn) Come on .
Code :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
typedef pair<int,int> P;
const ll MAXN=2000000;
ll prime[MAXN+10],notPrime[MAXN+10],mu[MAXN+10],tot;
void initMu(ll n)
{
notPrime[1]=mu[1]=1;
for(ll i=2;i<=n;i++)
{
if(!notPrime[i])prime[tot++]=i,mu[i]=-1;
for(ll j=0;j<tot&&i*prime[j]<=n;j++)
{
notPrime[i*prime[j]]=1;
if(i%prime[j])mu[i*prime[j]]=-mu[i];
else {
mu[i*prime[j]]=0;break;}
}
}
}
ll n;
ll getF(ll g)
{
ll t=n/g;
return (t*t-t)/2;
}
int main()
{
initMu(MAXN);
scanf("%lld",&n);
ll ans=0;
for(ll g=1;g<=n;g++)
{
for(ll d=g;d<=n;d+=g)
{
ans=ans+g*mu[d/g]*getF(d);
}
}
printf("%lld\n",ans);
return 0;
}
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425292.html
边栏推荐
- Amazon cloud technology entry Resource Center, easy access to the cloud from 0 to 1
- 个人主页软件Fenrus
- MySQL - Chapter 1 (data types in MySQL)
- Flutter 的加载动画这么玩更有趣
- MySQL of database -- overview and installation
- JSON input of Chapter 14 of kettle paoding jieniu
- ALV tree (ll LR RL RR) insert delete
- Kernel PWN learning (3) -- ret2user & kernel ROP & qwb2018 core
- MySQL of database -- basic common query commands
- 653. Sum of two IV - input BST
猜你喜欢
Sql1 [geek challenge 2019]
AQS & reentrantlock implementation principle
Go language learning notes - structure | go language from scratch
Leetcode question bank 78 Subset (recursive C implementation)
三、6【Verilog HDL】基础知识之门级建模
Secrets in buffctf file 1
JS what is an event? Event three elements and operation elements
Installation of data cleaning ETL tool kettle
云身份过于宽松,为攻击者打开了大门
Random neurons and random depth of dropout Technology
随机推荐
Learn FPGA (from Verilog to HLS)
Creation of raid0 and RAID5 and Simulation of how RAID5 works
SAP ECC connecting SAP pi system configuration
108. 将有序数组转换为二叉搜索树
Chapter VIII project stakeholder management of information system project manager summary
JS DOM learn three ways to create elements
Two ways for flutter providers to share data
Exclusive thoughts and cases of JS
Kettle实验 转换案例
501. Mode in binary search tree
Random neurons and random depth of dropout Technology
Sql1 [geek challenge 2019]
Explanation of order and primitive root of number theory
Applet error: should have URL attribute when using navigateto, redirectto or switchtab
108. Convert an ordered array into a binary search tree
ABAP implementation publishes restful services for external invocation example
成功的DevOps Leader 应该清楚的3个挑战
1 + X cloud computing intermediate -- script construction, read-write separation
High paid programmer & interview question series 91 limit 20000 loading is very slow. How to solve it? How to locate slow SQL?
Node installation