Description
在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋，他惜财如命，因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的存款。该村子在财产上的求和运算等同于我们的乘法运算，也就是说领袖开户时的存款总和为3100000。这里发行的软妹面额是最小的60个素数（p1=2,p2=3,…,p60=281），任何人的财产都只能由这60个基本面额表示，即设某个人的财产为fortune（正整数），则fortune=p1^k1*p2^k2*......p60^K60。
领袖习惯将一段编号连续的银行里的存款拿到一个账房去清点，为了避免GFS串通账房叛变，所以他不会每次都选择同一个账房。GFS跟随领袖多年已经摸清了门路,知道领袖选择账房的方式。如果领袖选择清点编号在[a,b]内的银行财产，他会先对[a,b]的财产求和（计为product），然后在编号属于[1,product]的账房中选择一个去清点存款，检验自己计算是否正确同时也检验账房与GFS是否有勾结。GFS发现如果某个账房的编号number与product相冲，领袖绝对不会选择这个账房。怎样才算与product不相冲呢？若存在整数x,y使得number*x+product*y=1，那么我们称number与product不相冲，即该账房有可能被领袖相中。当领袖又赚大钱了的时候，他会在某个银行改变存款，这样一来相同区间的银行在不同的时候算出来的product可能是不一样的，而且领袖不会在某个银行的存款总数超过1000000。
现在GFS预先知道了领袖的清点存款与变动存款的计划，想请你告诉他，每次清点存款时领袖有多少个账房可以供他选择，当然这个值可能非常大，GFS只想知道对19961993取模后的答案。
Input
第一行一个整数x表示领袖清点和变动存款的总次数。
接下来x行，每行3个整数ai,bi,ci。ai为0时表示该条记录是清点计划，领袖会清点bi到ci的银行存款，你需要对该条记录计算出GFS想要的答案。ai为1时表示该条记录是存款变动，你要把银行bi的存款改为ci，不需要对该记录进行计算。
Output
输出若干行，每行一个数，表示那些年的答案。‘
看到这题，我们先不去管别的。。先把题意看懂！（说多了都是泪啊QAQ）
然后我们想一想，如果ax+by=1(a<b)的x，y的解，就说明gcd(a,b)==1.
那么就是求phi[b]..
然后就是维护区间的积？就是线段树啦。。
然后还可以维护一个区间的积的因数有哪些？不过好像很麻烦？
我们一算，60个质数，恩，1<<60，恩，没爆long long？
好吧，就是状态压缩一下吧。。之后用欧拉函数的因数求解方式。。
然后就ok啦。。说的这么简单，代码真是要爆炸了。。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 6 #define maxn 100001 7 8 #define mod 19961993 9 10 typedef long long ll; 11 12 using namespace std; 13 14 int prime[300],ff[300]; 15 16 ll inv[300],x,y; 17 18 bool is_prime[300]; 19 20 struct tr{ 21 int l,r; 22 ll ans,mark; 23 }tree[maxn*4]; 24 25 void exgcd(int n,int m) 26 { 27 if(m==0){x=1,y=0;return;} 28 exgcd(m,n%m); 29 ll t=x; 30 x=y,y=t-n/m*y; 31 } 32 33 void pre() 34 { 35 inv[1]=1; 36 int b=0; 37 for(int i=2;i<=281;i++) 38 { 39 if(!is_prime[i])prime[++b]=i,exgcd(i,mod),inv[i]=(x%mod+mod)%mod,ff[i]=b; 40 int j=1,t=2*i; 41 while(j<=b&&t<=281) 42 { 43 is_prime[t]=1; 44 if(i%prime[j]==0){break;} 45 t=prime[++j]*i; 46 } 47 } 48 return; 49 } 50 51 int read() 52 { 53 int x=0;char ch=getchar(); 54 while(ch<'0'||ch>'9')ch=getchar(); 55 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 56 return x; 57 } 58 59 void build(int l,int r,int num) 60 { 61 tree[num].mark=1<<2; 62 if(l==r){tree[num].l=tree[num].r=l;tree[num].ans=3;return;} 63 int mid=(l+r)>>1;build(l,mid,num<<1);build(mid+1,r,(num<<1)+1); 64 tree[num].l=l,tree[num].r=r,tree[num].ans=tree[num<<1].ans*tree[(num<<1)+1].ans%mod; 65 } 66 67 ll pow(int k) 68 { 69 ll x=2,ans=1; 70 while(k!=0) 71 { 72 if(k&1)ans=ans*x; 73 x=x*x; 74 k>>=1; 75 } 76 return ans; 77 } 78 79 void fen(int shu,int wei) 80 { 81 tree[wei].mark=0; 82 for(int i=2;i<=sqrt(shu);i++)if(shu%i==0&&!is_prime[i]){ 83 while(shu%i==0)shu/=i; 84 tree[wei].mark+=pow(ff[i]); 85 } 86 if(shu!=1)tree[wei].mark+=pow(ff[shu]); 87 } 88 89 void update(int wei,int des,int change) 90 { 91 if(tree[wei].l==tree[wei].r){ 92 tree[wei].ans=change; 93 fen(change,wei); 94 return; 95 } 96 int mid=(tree[wei].l+tree[wei].r)>>1; 97 if(mid>=des)update(wei<<1,des,change); 98 else update((wei<<1)+1,des,change); 99 tree[wei].ans=tree[(wei<<1)].ans*tree[(wei<<1)+1].ans%mod; 100 tree[wei].mark=tree[(wei<<1)].mark | tree[(wei<<1)+1].mark; 101 } 102 103 ll ans; 104 105 ll find(int l,int r,int num) 106 { 107 if(tree[num].l==l&&tree[num].r==r){ans=ans*tree[num].ans%mod;return tree[num].mark;} 108 int mid=(tree[num].l+tree[num].r)>>1; 109 if(mid>=r)return find(l,r,num<<1); 110 else if(mid<l)return find(l,r,(num<<1)+1); 111 else return find(l,mid,num<<1) | find(mid+1,r,(num<<1)+1); 112 } 113 114 ll solve(int l,int r) 115 { 116 ll state=find(l,r,1); 117 for(int i=1;i<=60;i++) 118 if(state>>i & 1)ans=(ans*(prime[i]-1)%mod*inv[prime[i]]%mod); 119 return ans; 120 } 121 122 int main() 123 { 124 int n; 125 pre(); 126 scanf("%d",&n); 127 build(1,100000,1); 128 for(int i=1;i<=n;i++) 129 { 130 bool doing=read(); 131 int x=read(),y=read(); 132 if(doing)update(1,x,y); 133 else ans=1,printf("%lld ",solve(x,y)); 134 } 135 return 0; 136 }
一定要看清题意！