由于之前做了Luogu P2257 YY的GCD，這里的做法就十分套路了。

建議先看上面一題的推導(dǎo)，這里的話就略去一些共性的地方了。

還是和之前一樣設(shè)：

\[f(d)=\sum_{i=1}^a \sum_{j=1}^b[\gcd(i,j)=d]\]

\[F(n)=\sum_{n|d} f(d)=\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor\]

還是莫比烏斯反演定理推出：

\[f(n)=\sum_{n|d}\mu(\lfloor\fracze8trgl8bvbq{n}\rfloor)F(d)\]

這時我們發(fā)現(xiàn)，不像上面一題那么繁瑣還要對\(f(n)\)求和，這里\(ans=f(d)\)

所以可以直接開始推導(dǎo)答案：

\[ans=\sum_{d|k}\mu(\lfloor\frac{k}ze8trgl8bvbq\rfloor)F(k)\]

還是考慮換個東西枚舉，我們設(shè)\(\lfloor\frac{k}ze8trgl8bvbq\rfloor=t\)，枚舉\(t\)則有：

\[ans=\sum_{t=1}^{\min(\lfloor\frac{a}ze8trgl8bvbq\rfloor,\lfloor\frac{b}ze8trgl8bvbq\rfloor)}\mu(t)\lfloor\frac{a}{t\cdot d}\rfloor\lfloor\frac{b}{t\cdot d}\rfloor\]

這個式子已經(jīng)變成\(O(n)\)的了，還是注意到\(\lfloor\frac{a}{t\cdot d}\rfloor\lfloor\frac{b}{t\cdot d}\rfloor\)可以除法分塊，然后只需要對莫比烏斯函數(shù)做一個前綴和即可單次\(O(\sqrt n)\)。

CODE

#include<cstdio> #include<cctype> #define RI register int using namespace std; const int P=50005; int t,n,m,d,prime[P+5],cnt,mu[P+5],sum[P+5]; long long ans; bool vis[P+5]; class FileInputOutput {private:#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)#define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))#define S 1<<21char Fin[S],Fout[S],*A,*B; int Ftop,pt[25];public:FileInputOutput() { A=B=Fin; Ftop=0; } inline void read(int &x){x=0; char ch; int flag=1; while (!isdigit(ch=tc())) flag=ch^'-'?1:-1;while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;}inline void write(long long x){if (!x) return (void)(pc(48),pc('\n')); RI ptop=0;while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc('\n');}inline void Fend(void){fwrite(Fout,1,Ftop,stdout);}#undef tc#undef pc#undef S }F; #define Pi prime[j] inline void Euler(void) {vis[1]=mu[1]=1; RI i,j; for (i=2;i<=P;++i){if (!vis[i]) prime[++cnt]=i,mu[i]=-1;for (j=1;j<=cnt&&i*Pi<=P;++j){vis[i*Pi]=1; if (i%Pi) mu[i*Pi]=-mu[i]; else break;}}for (i=1;i<=P;++i) sum[i]=sum[i-1]+mu[i]; } #undef Pi inline int min(int a,int b) {return a<b?a:b; } int main() {//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);for (Euler(),F.read(t);t;--t){F.read(n); F.read(m); F.read(d); ans=0; int lim=min(n/d,m/d);for (RI l=1,r;l<=lim;l=r+1){r=min(n/(n/l),m/(m/l)); ans+=1LL*(n/(l*d))*(m/(l*d))*(sum[r]-sum[l-1]);}F.write(ans);}return F.Fend(),0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cjjsb/p/9852467.html

總結(jié)

以上是生活随笔為你收集整理的Luogu P3455 [POI2007]ZAP-Queries的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。