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[...

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&lt...

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 ...

HDU 5692-Snacks 处理出每个节点到根节点的node[u]值,对于修改操作相当于对子树中的node值修改,查找时查找子树的最大值即可.dfs序转化成区间操作,线段树查找最大值. #pragma comment(linker, "/STACK:1024000000,1024000000") #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",s...

HDU 5212-Code #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 << dou...

HDU-5382 GCD?LCM! #include<bits/stdc++.h> #define sc scanf using namespace std; const int N=1e6+77; const int mod=258280327; typedef long long ll; int prime[N],mu[N],tot=0; bool vis[N]; ll A[N],B[N],C[N],D[N]; void f_mod(ll &x){ if(x>=mod)x-=x/mod*mod; if(x<0)x=(x%mod+...

HDU-5628 Clarke and math . #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();co...

最大流最小割 #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int inf=1e9; int n,m,x,y,z,maxflow,deep[500];//deep深度 struct Edge{ int next,to,dis; }edge[500]; int num_edge=-1,head[500],cur[500];//cur用于复制head queue <int> q; v...