莫比乌斯函数，欧拉函数，，，，。 为的不同素因子个数，为的所有素因子个数。。

Easy Problem     当时现场赛因为题我推的公式，化简的时候，出现了这个错误，导致找bug找了2个小时。A掉之后已经没有时间写题了，学了这么久的数论，题真的是再简单不过的反演了，但是策略有问题，加上化简公式时出现的错误，没来的及写，真的很可惜。 最后用欧拉降幂，线性筛即可。   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf using namespace std; const int N=1e5+5; const int mod=59964251; typed...

HDU-6363 bookshelf  Patrick Star bought a bookshelf, he named it ZYG !! Patrick Star has book . The ZYG has layers (count from to ) and there is no limit on the capacity of each layer ! Now Patrick want to put all books on ZYG : 1. Assume that the i-th layer has books finally. 2. Assume that is the ...

GCD Array  Teacher Mai finds that many problems about arithmetic function can be reduced to the following problem:Maintain an array a with index from to . There are two kinds of operations:  Add to for every that . Query     插入操作：  2. 查询操作：    #include<bits/stdc++.h> #define me(a,x) memset(a,x...

Divisor Sums

codeforces-839D Winter is here     设，则答案可以表示为设，设的倍数个数为,则。所以有，反演得。   #include<bits/stdc++.h> using namespace std; const int N=1e6+6; const int p=1e9+7; typedef long long ll; ll ksm(ll a,ll b){ll ans=1;for(;b>0;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;} short int mu[N]; int flag[...

codeforces-1017F The Neutral Zone     这题内存限制只有16MB,考虑将2和3的倍数筛去，剩下的数只有1e8个，然后用bitset做标记数组，内存就只需要12MB.标记的数字下标刚好是i/3.   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); #define sc scanf #define itn int...

HDU-6134 Battlestation Operational       #include<bits/stdc++.h> using namespace std; const int N=1e6+6; const int p=1e9+7; typedef long long ll; short int mu[N]; bool vis[N]; int prime[N],tot=0; ll phi[N],f[N],g[N]; void pre(){ phi[1]=mu[1]=1; for(int i=2;i<N;i++){ if(!vis[i])prime[++tot]=...

GCD of Divisors

HDU-6102 GCDispower  给定一个的一个排列，有个查询。每次询问输出   离线处理,对于每次的询问,等价于求. 可以考虑枚举，讲右端点固定，那么对于这个区间中，所有的后 互相互质的对数乘，就是对左端点，所有区间的贡献。 将的倍数且位置小于的数筛出来后，考虑从大到小枚举，每次求与中互质的个数乘 也就是 是从大到小扫过之后整除的个数。利用树状数组区间修改，最后查询每个的值就行。   #include<bits/stdc++.h> using namespace std; #define IN freopen("in.txt","r",stdin); const int ...

Product        #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); #define sc scanf #define itn int #define STR clock_t startTime = clock(); #define END clock_t endTime = clock();cout << double(e...

LCMs  We have an integer sequence of length Find the following sum:         #include<bits/stdc++.h> using namespace std; const int N=1e6+5; const int p=998244353; typedef long long ll; int n,a[N],f[N]={0}; short int mu[N]; ll inv[N],w[N]; int main(){ mu[1]=1;inv[1]=1; for(int i=2;i<N;i++)in...

UVA 12546-LCM Pair Sum     #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); #define STR clock_t startTime = clock(); #define END clock_t endTime = clock();cout <&...

HDU 5877-Weak Pair     相当于子树中有多少个点满足,dfs序列之后就是区间查找了.   #include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); #define sc scanf #define itn int #define STR clock_t startTime = clock(); #define END clock_t ...