【线段树/数学/扩展欧几里得】 Bzoj 3913:奇数国

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啦。。说的这么简单，代码真是要爆炸了。。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define maxn 100001

 #define mod 19961993

 typedef long long ll;

 using namespace std;

 int prime[],ff[];

 ll inv[],x,y;

 bool is_prime[];

 struct tr{

     int l,r;

     ll ans,mark;

 }tree[maxn*];

 void exgcd(int n,int m)

 {

     if(m==){x=,y=;return;}

     exgcd(m,n%m);

     ll t=x;

     x=y,y=t-n/m*y;

 }

 void pre()

 {

     inv[]=;

     int b=;

     for(int i=;i<=;i++)

     {

         if(!is_prime[i])prime[++b]=i,exgcd(i,mod),inv[i]=(x%mod+mod)%mod,ff[i]=b;

         int j=,t=*i;

         while(j<=b&&t<=)

         {

             is_prime[t]=;

             if(i%prime[j]==){break;}

             t=prime[++j]*i;

         }

     }

     return;

 }

 int read()

 {

     int x=;char ch=getchar();

     while(ch<''||ch>'')ch=getchar();

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x;

 }

 void build(int l,int r,int num)

 {

     tree[num].mark=<<;

     if(l==r){tree[num].l=tree[num].r=l;tree[num].ans=;return;}

     int mid=(l+r)>>;build(l,mid,num<<);build(mid+,r,(num<<)+);

     tree[num].l=l,tree[num].r=r,tree[num].ans=tree[num<<].ans*tree[(num<<)+].ans%mod;

 }

 ll pow(int k)

 {

     ll x=,ans=;

     while(k!=)

     {

         if(k&)ans=ans*x;

         x=x*x;

         k>>=;

     }

     return ans;

 }

 void fen(int shu,int wei)

 {

     tree[wei].mark=;

     for(int i=;i<=sqrt(shu);i++)if(shu%i==&&!is_prime[i]){

         while(shu%i==)shu/=i;

         tree[wei].mark+=pow(ff[i]);

     }

     if(shu!=)tree[wei].mark+=pow(ff[shu]);

 }

 void update(int wei,int des,int change)

 {

     if(tree[wei].l==tree[wei].r){

         tree[wei].ans=change;

         fen(change,wei);

         return;

     }

     int mid=(tree[wei].l+tree[wei].r)>>;

     if(mid>=des)update(wei<<,des,change);

     else update((wei<<)+,des,change);

     tree[wei].ans=tree[(wei<<)].ans*tree[(wei<<)+].ans%mod;

     tree[wei].mark=tree[(wei<<)].mark | tree[(wei<<)+].mark;

 }

 ll ans;

 ll find(int l,int r,int num)

 {

     if(tree[num].l==l&&tree[num].r==r){ans=ans*tree[num].ans%mod;return tree[num].mark;}

     int mid=(tree[num].l+tree[num].r)>>;

     if(mid>=r)return find(l,r,num<<);

     else if(mid<l)return find(l,r,(num<<)+);

     else return find(l,mid,num<<) | find(mid+,r,(num<<)+);

 }

 ll solve(int l,int r)

 {

     ll state=find(l,r,);

     for(int i=;i<=;i++)

         if(state>>i & )ans=(ans*(prime[i]-)%mod*inv[prime[i]]%mod);

     return ans;

 }

 int main()

 {

     int n;

     pre();

     scanf("%d",&n);

     build(,,);

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

     {

         bool doing=read();

         int x=read(),y=read();

         if(doing)update(,x,y);

         else ans=,printf("%lld\n",solve(x,y));

     }

     return ;

 }

　　一定要看清题意！

巴特西

【线段树/数学/扩展欧几里得】 Bzoj 3913:奇数国

Description

Input

Output

最新文章

热门文章