第九场
也是打的很烂，赛时签到场
签到：A,K略过
I:
C:
首先试图打表1e5大失败（小丑）。然后我们发现修改后每个点的值应该为\(r[i]*c[j]*gcd(i,j)\),假设gcd(i,j)全为1，那么整个矩阵的和值就是\((r[1]+r[2]+...+r[n])（c[1]+c[2]+..+c[n])\)。也就是说，对于值全为1
的n*n矩阵在进行行列乘法的时候是可以直接计算出ans的。
于是就想到可以把整个矩阵拆分为若干a[i][j]相等的小矩阵进行计算，列式为\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)*c[i]*r[j]\)。
推出这个结论以后就是一个比较板的，可以用欧拉函数（特解）或是莫比乌斯反演（通解）写的一个题。（代码显然是欧拉函数
已知若\(gcd(i,j)=d\),则\(gcd(i,j)=\sum\phi(d)\)。
\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n}（\sum\phi(d)）*c[i]*r[j]\)
对于所有含gcd的题目都应该把gcd提前，则\(ans=\sum_{d=1}^n\phi(d)*\sum_{i=1}^{n/d}c[i]*\sum_{j=1}^{n/d}r[j]\)
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e5+10;
int phi[maxn],p[maxn],pw,ans,sc[maxn],sr[maxn],ctc[maxn],ctr[maxn];
vector<int>d[maxn];
bool vis[maxn];
void add(int &x,int y){
x=(x+y)%mod;
}
void getPhi() {
phi[1]=1;
for(int i=2;i<maxn;i++){
if(!phi[i]){
phi[i]=i-1;
p[++pw]=i;
}
for(int j=1;j<=pw&&p[j]*i<maxn;j++){
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
getPhi();
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
ctc[i]=1;ctr[i]=1;
for(int j=i;j<=n;j+=i){
d[j].push_back(i);
add(sc[i],1);
add(sr[i],1);
}
add(ans,1ll*phi[i]*sc[i]%mod*sr[i]%mod);
}
while(m--){
char c;int x,y;
cin>>c>>x>>y;
for(int i:d[x]){
add(ans,mod-1ll*phi[i]*sc[i]%mod*sr[i]%mod);
add(sc[i],mod-ctc[x]);
add(sr[i],mod-ctr[x]);
}
if(c=='R')ctr[x]=1ll*ctr[x]*y%mod;
else ctc[x]=1ll*ctc[x]*y%mod;
for(int i:d[x]){
add(sc[i],ctc[x]);
add(sr[i],ctr[x]);
add(ans,1ll*phi[i]*sc[i]%mod*sr[i]%mod);
}
cout<<ans<<"\n";
}
}