wordpress评论删除站点,重庆渝云建设有限公司,网页设计实训心得体会300字,互联网公司排名朗玛正题
P3455 题目大意
有T组询问#xff0c;每组询问给出n,m,c#xff0c;求∑i1n∑j1m[(i,j)c]\sum_{i1}^{n}\sum_{j1}^{m}[(i,j)c]i1∑nj1∑m[(i,j)c] 解题思路
可以先对n,m除c这样就使得求出的数都有c的因子#xff0c;得到式子如下 ∑i1n∑j1m[(i,j)1]∑i1n∑j1m∑…正题
P3455 题目大意
有T组询问每组询问给出n,m,c求∑i1n∑j1m[(i,j)c]\sum_{i1}^{n}\sum_{j1}^{m}[(i,j)c]i1∑nj1∑m[(i,j)c] 解题思路
可以先对n,m除c这样就使得求出的数都有c的因子得到式子如下 ∑i1n∑j1m[(i,j)1]∑i1n∑j1m∑d∣i,d∣jμ(d)∑d1min(n,m)μ(d)×⌊nd⌋×⌊md⌋\sum_{i1}^{n}\sum_{j1}^{m}[(i,j)1]\\ \sum_{i1}^{n}\sum_{j1}^{m}\sum_{d|i,d|j}\mu(d)\\ \sum_{d1}^{min(n,m)}\mu(d)\times \left\lfloor\frac{n}{d}\right\rfloor\times \left\lfloor\frac{m}{d}\right\rfloor i1∑nj1∑m[(i,j)1]i1∑nj1∑md∣i,d∣j∑μ(d)d1∑min(n,m)μ(d)×⌊dn⌋×⌊dm⌋ 然后整除分块求解
时间复杂度O(Tn)O(T\sqrt{n})O(Tn) code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 50050
using namespace std;
int T,n,m,d,w,ans,mu[N],p[N],prime[N];
void work()
{p[1]1;mu[1]1;for(int i2;i50000;i){if(!p[i]){prime[w]i;mu[i]-1;}for(int j1;jwi*prime[j]50000;j){p[i*prime[j]]1;if(i%prime[j]0){mu[i*prime[j]]0;break;}else mu[i*prime[j]]-mu[i];}}for(int i2;i50000;i)mu[i]mu[i-1];return;
}
int main()
{work();scanf(%d,T);while(T--){scanf(%d%d%d,n,m,d);n/d;m/d;ans0;for(int l1,r0;lmin(n,m);lr1){rmin(n/(n/l),m/(m/l));ans(mu[r]-mu[l-1])*(n/l)*(m/l);}printf(%d\n,ans);}return 0;
}
