HYSBZ

　　中文题，巨苟题，巨无敌苟！！首先是关于不相冲数，也就是互质数的处理，欧拉函数是可以求出互质数，但是这里的product非常大，最小都2^100000，这是不可能实现的。所以我们要求互质数的话，得用到所有金额都用60个素数表示的这个条件。也就是x=p₁^a1xp₂^a2x...p₆₀^a60表示，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(p1^a1)的话，p1是质数，然后p1^a1=p1^a1-1*p1,而p1^a1-1 mod p1=0，所以phi(p1^a1)=phi(p1^a1-1)*p1,又phi(p1^a1-1)=phi(p1^a1-2)*p1，一直到，phi(p1)=p1-1,所以phi(p1^a1)=p1^a1-1*(p1-1),

　　然后求phi(p1^a1*p2)，p1^a1 mod p2≠0，所以phi(p1^a1*p2)=phi(p1^a1)*(p2-1)，再算phi(p1^a1*p2²)，p1^a1*p2² mod p2=0，所以phi(p1^a1*p2²)=phi(p1^a1*p2)*p2，所以这样推下去的话，phi(p1^a1*p2^a2)=p1^a1-1*(p1-1)*p2^a2-1*(p2-1)

　　我们可以得到phi(p₁^a1xp₂^a2x...p₆₀^a60)=p1^a1-1*(p1-1)*p2^a2-1*(p2-1)*...*p₆₀^a60-1*(p₆₀-1)。

　　因为它说这个国家的加法就是我们的乘法，所以我们可以用树状数组或者线段树来维护1~100000里存储的每个数对应的素数的次方，但第二苟的点来了，如果用线段树还好说，只要处理好懒标记就应该可以了，但是用树状数组，单点更新那里一不小心就会超时，超时了好几发后，我看学长的代码原来他们的树状数组也是9492ms险过的，先看AC代码，更新处是使用学长的处理。

 1 #include<cstdio>
 2 #define lowb(x) x&(-x)
 3 #define ll long long
 4 const int  N=100000;
 5 const ll mod=19961993;
 6 int a[N+18][66]={0},b[N],prime[66]={
 7 0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
 8 71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,
 9 149,151,157,163,167,173,179,181,191,193,197,199,211,223,
10 227,229,233,239,241,251,257,263,269,271,277,281};//我自己把素数打出来了 
11 void updata(int x,int y,int z)
12 {
13     while(x<=N)
14     {
15         a[x][y]+=z;
16         x+=lowb(x);
17     }
18 }
19 int geta(int x,int y)
20 {
21     int ans=0;
22     while(x)
23     {
24         ans+=a[x][y];
25         x-=lowb(x);
26     }
27     return ans;
28 }
29 void modify(int x,int y,int flag)
30 {
31     for(int i=1;i<=60;i++)//把价值转化成p1^a1+p2^a2+p3^a3+...+p60^a60的形式，然后存储指数ai 
32         if(y%prime[i]==0)
33         {
34             int z=0;
35             while(y%prime[i]==0)
36             {
37                 z++;
38                 y/=prime[i];
39             }
40             updata(x,i,flag*z);
41         }
42 }
43 ll pow(ll a,int b)
44 {
45     ll ans=1;
46     a%=mod;
47     while(b)
48     {
49         if(b&1)
50             ans=(ans*a)%mod;
51         a=(a*a)%mod;
52         b>>=1;
53     }
54     return ans;
55 }
56 int main()
57 {
58     int n,op,x,y,z;
59     scanf("%d",&n);
60     for(int i=1;i<=N;i++)
61     {
62         b[i]=3;
63         updata(i,2,1);//3是第二个素数，一开始每个都有3块钱 
64     }
65     while(n--)
66     {
67         scanf("%d%d%d",&op,&x,&y);
68         if(op)
69         {
70             modify(x,b[x],-1);//先减去原来的数 
71             modify(x,y,1);//再加上要修改的数 
72             b[x]=y;
73         }
74         else
75         {
76             ll ans=1;
77             for(int i=1;i<=60;i++)
78             {
79                 z=geta(y,i)-geta(x-1,i);
80                 if(z)
81                     ans=ans*pow(1ll*prime[i],z-1)*(prime[i]-1)%mod;
82             }
83             printf("%lld
",ans);
84         }
85     }
86     return 0;
87 }

学长好腻害哦

　　学长的处理就是，保存好每一个原来的存款，然后每次更新时，先减去旧的存款然后再加上新的存款，而我的处理的话是

 1 for(int i=1;i<=60;i++)
 2 {
 3     z=0;
 4     while(y%prime[i]==0)
 5     {
 6         z++;
 7         y/=prime[i];    
 8     }
 9     z=z-a[x][i];//原来新的指数和对旧的指数差值，正的说明要加上，负的说明要减去，0不需要更新
10     if(z!=0)
11     　　updata(x,i,z);    
12 }

　　我觉得我这样每个i只进行了一次更新，应该比学长的更快，然而T了，我觉得原因应该是在于如果z不是0的话，那么我的就是60遍每次都要从x节点更新到100000为止，但学长的看上去是跑了两边，但是if(y%prime[i]==0)这一句过滤掉很多没必要的更新，所以还是学长nb啊。。。

　　至于线段树的做法，先留个坑，毕竟女同志能顶半边天。