HYSBZ - 3813奇数国
中文题，巨苟题，巨无敌苟！！首先是关于不相冲数，也就是互质数的处理，欧拉函数是可以求出互质数，但是这里的product非常大，最小都2100000，这是不可能实现的。所以我们要求互质数的话，得用到所有金额都用60个素数表示的这个条件。也就是x=p1a1xp2a2x...p60a60表示，pi是第i个素数,ai是对应的指数，这就变成了互质素求欧拉函数，可以先了解一下欧拉函数，引用一下*大佬的博客欧拉函数的讲解。我们需要用到这一条
p为质数
1. phi(p)=p-1 因为质数p除了1以外的因数只有p，故1至p的整数只有p与p不互质
2. 如果i mod p = 0, 那么 phi(i * p)=phi(i) * p
3.若i mod p ≠0, 那么 phi( i * p )=phi(i) * ( p-1 )
首先，如果我们要求phi(p1a1)的话，p1是质数，然后p1a1=p1a1-1*p1,而p1a1-1 mod p1=0，所以phi(p1a1)=phi(p1a1-1)*p1,又phi(p1a1-1)=phi(p1a1-2)*p1，一直到，phi(p1)=p1-1,所以phi(p1a1)=p1a1-1*(p1-1),
然后求phi(p1a1*p2)，p1a1 mod p2≠0，所以phi(p1a1*p2)=phi(p1a1)*(p2-1)，再算phi(p1a1*p22)，p1a1*p22 mod p2=0，所以phi(p1a1*p22)=phi(p1a1*p2)*p2，所以这样推下去的话，phi(p1a1*p2a2)=p1a1-1*(p1-1)*p2a2-1*(p2-1)
我们可以得到phi(p1a1xp2a2x...p60a60)=p1a1-1*(p1-1)*p2a2-1*(p2-1)*...*p60a60-1*(p60-1)。
因为它说这个国家的加法就是我们的乘法，所以我们可以用树状数组或者线段树来维护1~100000里存储的每个数对应的素数的次方，但第二苟的点来了，如果用线段树还好说，只要处理好懒标记就应该可以了，但是用树状数组，单点更新那里一不小心就会超时，超时了好几发后，我看学长的代码原来他们的树状数组也是9492ms险过的，先看AC代码，更新处是使用学长的处理。
#include<cstdio>
#define lowb(x) x&(-x)
#define ll long long
const int N=;
const ll mod=;
int a[N+][]={},b[N],prime[]={
,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,
,,,,,,,,,,,};//我自己把素数打出来了
void updata(int x,int y,int z)
{
while(x<=N)
{
a[x][y]+=z;
x+=lowb(x);
}
}
int geta(int x,int y)
{
int ans=;
while(x)
{
ans+=a[x][y];
x-=lowb(x);
}
return ans;
}
void modify(int x,int y,int flag)
{
for(int i=;i<=;i++)//把价值转化成p1^a1+p2^a2+p3^a3+...+p60^a60的形式，然后存储指数ai
if(y%prime[i]==)
{
int z=;
while(y%prime[i]==)
{
z++;
y/=prime[i];
}
updata(x,i,flag*z);
}
}
ll pow(ll a,int b)
{
ll ans=;
a%=mod;
while(b)
{
if(b&)
ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=;
}
return ans;
}
int main()
{
int n,op,x,y,z;
scanf("%d",&n);
for(int i=;i<=N;i++)
{
b[i]=;
updata(i,,);//3是第二个素数，一开始每个都有3块钱
}
while(n--)
{
scanf("%d%d%d",&op,&x,&y);
if(op)
{
modify(x,b[x],-);//先减去原来的数
modify(x,y,);//再加上要修改的数
b[x]=y;
}
else
{
ll ans=;
for(int i=;i<=;i++)
{
z=geta(y,i)-geta(x-,i);
if(z)
ans=ans*pow(1ll*prime[i],z-)*(prime[i]-)%mod;
}
printf("%lld\n",ans);
}
}
return ;
}
学长好腻害哦
学长的处理就是，保存好每一个原来的存款，然后每次更新时，先减去旧的存款然后再加上新的存款，而我的处理的话是
for(int i=;i<=;i++)
{
z=;
while(y%prime[i]==)
{
z++;
y/=prime[i];
}
z=z-a[x][i];//原来新的指数和对旧的指数差值，正的说明要加上，负的说明要减去，0不需要更新
if(z!=)
updata(x,i,z);
}
我觉得我这样每个i只进行了一次更新，应该比学长的更快，然而T了，我觉得原因应该是在于如果z不是0的话，那么我的就是60遍每次都要从x节点更新到100000为止，但学长的看上去是跑了两边，但是if(y%prime[i]==0)这一句过滤掉很多没必要的更新，所以还是学长nb啊。。。
至于线段树的做法，先留个坑，毕竟女同志能顶半边天。