1 条题解
-
0
问题
有一张 的数表，其第 行第 列的数值为能同时整除 和 的所有自然数之和。 有T次询问，每次询问给定 ，计算数表 至 中不大于 的数之和（）。每组数据输出一行一个整数，表示答案模 的值。
题解
$\sum\limits_{i=1}^n\sum\limits_{j=1}^m f(\gcd(i,j)) \lbrack f(\gcd(i,j)) \leq A \rbrack$
表示 所有约数和。假设先忽略条件 的限制
设$\sum\limits_{i=1}^n\sum\limits_{j=1}^m f(\gcd(i,j))$ $=\sum\limits_{d=1}^n \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}} f(d)\lbrack\gcd(i,j)=1\rbrack$ $=\sum\limits_{d=1}^n f(d）\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}\sum\limits_{a|\gcd(i,j)}\mu(a)$ $=\sum\limits_{d=1}^n f(d) \sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}\sum\limits_{a=1}^{\frac{n}{d}} \lbrack a|i \rbrack \lbrack a|j \rbrack \mu(a)$ $=\sum\limits_{d=1}^n f(d) \sum\limits_{a=1}^{\frac{n}{d}}\mu(x)\sum\limits_{i=1}^{\frac{n}{d}}\lbrack a|i \rbrack\sum\limits_{j=1}^{\frac{m}{d}}\lbrack a|j \rbrack$ $=\sum\limits_{d=1}^n f(d) \sum\limits_{a=1}^{\frac{n}{d}}\mu(a)\lfloor\frac{n}{ad}\rfloor\lfloor\frac{m}{ad}\rfloor$ 设 $=\sum\limits_{d=1}^n f(d) \sum\limits_{\frac{T}{d}=1}^{\frac{n}{d}}\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T} \rfloor$ $=\sum\limits_{d=1}^n f(d) \sum\limits_{T=1}^n\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$ $=\sum\limits_{T=1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum\limits_{d|T}f(d) \mu(\frac{T}{d})$ 设 $F(T)=\sum\limits_{d 具体代码如下：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5,M=2e4; const LL mod=(1ll<<31); int pr,p[N+10];LL mu[N+10],g[N+10];bool v[N+10];//g[i]为i的最小质因数等比序列和 struct node{int x;LL c;} f[N+10];//f[?]表示为f[?].x的所有约数和为f[?].c void init() { memset(v,0,sizeof(v)); pr=0;mu[1]=1;g[1]=1;f[1]={1,1}; for(int i=2;i<=N;i++) { if(!v[i]){p[++pr]=i,mu[i]=-1,g[i]=i+1,f[i]={i,i+1};} for(int j=1;j<=pr&&i*p[j]<=N;j++) { int x=i*p[j]; v[x]=1; if(i%p[j]==0) { mu[x]=0; g[x]=g[i]*p[j]+1; f[x]={x,f[i].c/g[i]*g[x]}; break; } mu[x]=-mu[i]; g[x]=p[j]+1; f[x]={x,f[i].c*(p[j]+1)}; } } sort(f+1,f+1+N,[](const node &a,const node &b){return a.c<b.c;}); } int c[N+10]; void add(int x,int k){for(;x<=N;x+=x&-x)c[x]+=k;} int query(int x){int res=0;for(;x;x-=x&-x)res+=c[x];return res;} struct que{int n,m,a,id;}Q[M+10]; LL calc(int n,int m) { if(n>m)swap(n,m); LL res=0; for(int l=1,r;l<=n;l=r+1) { r=min(n/(n/l),m/(m/l)); res=res+(query(r)-query(l-1))*(n/l)*(m/l); } return res; } LL ans[M+10]; int main() { init(); int T;scanf("%d",&T); for(int i=1;i<=T;i++)scanf("%d",&Q[i].n),scanf("%d",&Q[i].m),scanf("%d",&Q[i].a),Q[i].id=i; sort(Q+1,Q+1+T,[](const que &a,const que &b){return a.a<b.a;}); memset(c,0,sizeof(c)); for(int i=1,j=1;i<=T;i++) { while(f[j].c<=Q[i].a&&j<=N) { for(int k=f[j].x;k<=N;k+=f[j].x) add(k,f[j].c*mu[k/f[j].x]); j++; } ans[Q[i].id]=calc(Q[i].n,Q[i].m); } for(int i=1;i<=T;i++)printf("%d\n",ans[i]%mod); return 0; }
- 1
