[bzoj4815] [洛谷P3700] [Cqoi2017] 小Q的表格

Description###

小Q是个程序员。

作为一个年轻的程序员，小Q总是被老C欺负，老C经常把一些麻烦的任务交给小Q来处理。

每当小Q不知道如何解决时，就只好向你求助。为了完成任务，小Q需要列一个表格，表格

有无穷多行，无穷多列，行和列都从1开始标号。为了完成任务，表格里面每个格子都填了

一个整数，为了方便描述，小Q把第a行第b列的整数记为f(a,b),为了完成任务，这个表格要

满足一些条件：

(1)对任意的正整数a,b,都要满足f(a,b)=f(b,a)；

(2)对任意的正整数a,b,都要

满足b×f(a,a+b)=(a+b)*f(a,b)。为了完成任务，一开始表格里面的数很有规律，第a行第b列的

数恰好等于a*b，显然一开始是满足上述两个条件的。为了完成任务，小Q需要不断的修改表

格里面的数，每当修改了一个格子的数之后，为了让表格继续满足上述两个条件，小Q还需要

把这次修改能够波及到的全部格子里都改为恰当的数。由于某种神奇的力量驱使，已经确保了

每一轮修改之后所有格子里的数仍然都是整数。为了完成任务，小Q还需要随时获取前k行前k

列这个有限区域内所有数的和是多少，答案可能比较大，只需要算出答案mod1,000,000,007

之后的结果。

Input###

第1行包含两个整数m,n,表示共有m次操作，所有操作和查询涉及到的行编号和列编号都不超过n。

接下来m行，每行4个整数a,b,x,k表示把第a行b列的数改成x，然后把它能够波及到的所有格子全

部修改，保证修改之后所有格子的数仍然都是整数，修改完成后计算前k行前k列里所有数的和。

1<=m<=10000,1<=a,b,k<=N<=4*10^6,0<=x<=1018

Output###

输出共m行，每次操作之后输出1行，表示答案mod 1,000,000,007之后的结果。

Sample Input###

3 3

1 1 1 2

2 2 4 3

1 2 4 2

Sample Output###

一开始,表格的前3行前3列如图中左边所示,前2次操

作后表格没有变化,第3次操作之后的表格如右边所示。

1 2 3 2 4 6

2 4 6 4 4 12

3 6 9 6 12 9

简要题解##

观察表格，可发现

\[\begin{equation*}
f(a,b)=f(gcd(a,b),gcd(a,b)) \cdot \frac{a}{gcd(a,b)} \cdot \frac{b}{gcd(a,b)}
\end{equation*}
\]

于是我们只需记下\(f(i,i)\)的值即可

利用欧拉函数计算答案，分块维护

想法##

手动模拟表格，至少花了30分钟我才发现

\[\begin{equation*}
f(a,b)=f(gcd(a,b),gcd(a,b)) \cdot \frac{a}{gcd(a,b)} \cdot \frac{b}{gcd(a,b)}
\end{equation*}
\]

发现结论的我大呼：妙题！

然后很尴尬地发现我不会做了…无奈只好翻题解

由上面的式子可知，我们只需记下所有\(f(i,i)\)，其他所有\(f\)值就都可以求出来了

查询时

\[\begin{equation*}
ans=\sum\limits_{i=1}^k f(i,i) \cdot [\sum\limits_{x=1}^{k/i} \sum\limits_{y=1}^{k/i} xy \cdot (gcd(x,y)==1)]
\end{equation*}
\]

我们记

\[\begin{equation*}
\begin{aligned}
g(n)&=\sum\limits_{x=1}^n \sum\limits_{y=1}^n xy \cdot (gcd(x,y)==1)\\
&=2\sum\limits_{x=1}^n \sum\limits_{y=1}^x xy \cdot (gcd(x,y)==1) - \sum\limits_{x=1}^n x^2 \cdot (gcd(x,x)==1) \\
&=2\sum\limits_{x=1}^n \sum\limits_{y=1}^x xy \cdot (gcd(x,y)==1) - 1
\end{aligned}
\end{equation*}
\]

再记

\[\begin{equation*}
\begin{aligned}
h(n) &=\sum\limits_{y=1}^n ny \cdot (gcd(n,y)==1) \\
&=n \sum\limits_{y=1}^n y \cdot (gcd(n,y)==1) \\
\end{aligned}
\end{equation*}
\]

这个式子可以理解为，1~n中所有与n互质的数的和 × n

有欧拉函数 \(\varphi(n)\) 表示n以内与n互质的数的个数

我们知道，若x与n互质，则n-x也与n互质。

也就是说与n互质的数可两两配对，和为n。

那么

\[\begin{equation*}
h(n)=\frac{\varphi(n) \cdot n^2}{2}
\end{equation*}
\]

故

\[\begin{equation*}
g(n)=2 \sum\limits_{x=1}^n h(x) - 1
\end{equation*}
\]

那么

\[\begin{equation*}
ans=\sum\limits_{i=1}^k f(i,i) \cdot g(k/i)
\end{equation*}
\]

由于我们知道 \(k/i\) 只有 \(\sqrt{n}\) 种取值

于是就可以愉快地分块 \(f(i,i)\) 啦！

设计一个 \(O(\sqrt{n})\) 修改， \(O(1)\) 查询的分块结构就好了……

代码##

注：调了若干次才终于对…心好累

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#define P 1000000007

using namespace std;

typedef long long ll;

const int N = 4000005;

const int SN = 4005;

ll phi[N];

int prime[N],pnum;

int n,sn,block;

void getphi(){

    phi[1]=1;

    for(int i=2;i<=n;i++) phi[i]=i-1;

    for(int i=2;i<=n;i++){

        if(phi[i]==i-1) prime[pnum++]=i;

        for(int j=0;j<pnum && (ll)prime[j]*i<=n;j++){

            if(i%prime[j]==0){

                phi[i*prime[j]]=phi[i]*prime[j];

                break;

            }

            phi[i*prime[j]]=phi[i]*(prime[j]-1);

        }

        phi[i]=(phi[i-1]+(ll)i*i%P*phi[i])%P; //g(i)

    }

}

ll num[N],add[SN];

ll query(int x){

    if(!x) return 0;

    int bl=(x-1)/sn+1;

    return (num[x]+add[bl])%P;

}

void change(int x,ll c){

    int bl=(x-1)/sn+1;

    for(int i=x;i<=min(bl*sn,n);i++) num[i]=(num[i]+c)%P;

    for(int i=bl+1;i<=block;i++) add[i]=(add[i]+c)%P;

}

int gcd(int a,int b) { return b ? gcd(b,a%b) : a; }

int main()

{

    int m;

    scanf("%d%d",&m,&n);

    sn=(int)sqrt(n); block=(n-1)/sn+1;

    for(int i=1;i<=n;i++) num[i]=(num[i-1]+(ll)i*i%P)%P;

    getphi();

    int a,b,k,g;

    ll ans=0,x,X;

    while(m--){

        scanf("%d%d%lld%d",&a,&b,&x,&k);

        if(a<b) swap(a,b);

        g=gcd(a,b);

        X=(x/(1ll((ll)a/g)*(b/g)))%P;  //罪魁祸首！！就是这里！！！

        change(g,(X-(query(g)-query(g-1)+P)%P+P)%P);

        ans=0;

        for(int l=1,r;l<=k;l=r+1){

            r=k/(k/l);

            ans=(ans+(query(r)-query(l-1)+P)%P*phi[k/l]%P)%P;

        }

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西