1 //0924 candy 2 //by Cydiater 3 //2016.9.24 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue>10 #include <map>11 #include <ctime>12 #include <cmath>13 #include <cstdlib>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n)        for(int i=j;i<=n;i++)18 #define down(i,j,n)        for(int i=j;i>=n;i--)19 #define FILE "candy"20 const ll MAXN=1e6+5;21 const ll oo=10000000LL;22 inline ll read(){23     char ch=getchar();ll x=0,f=1;24     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26     return x*f;27 }28 ll N,M,flag,ans=0,cnt=0;29 priority_queue<ll>A,B;30 namespace solution{31     ll gcd(ll a,ll b){32         if(b==0)return a;33         ans+=a/b*b;34         return gcd(b,a%b);35     }36     void init(){37         N=read();M=read();flag=read();38     }39     void slove(){40         gcd(max(N,M),min(N,M));41         cout<<ans<<endl;42         if(flag==1){43             up(i,1,M)A.push(N);44             up(i,1,N)B.push(M);45             while(1){46                 if(A.size()==0||B.size()==0)break;47                 if(A.size()>B.size())swap(A,B);48                 ll len=A.size();49                 up(i,1,len){50                     int num=B.top();B.pop();51                     int tmp=A.top();A.pop();52                     if(tmp-num!=0)A.push(tmp-num);53                     printf("%d ",num);54                 }55             }56             puts("");57         }58     }59 }60 int main(){61     freopen(FILE".in","r",stdin);62     freopen(FILE".out","w",stdout);63     using namespace solution;64     init();65     slove();66     return 0;67 }

 1 //0924 gcd 2 //by Cydiater 3 //2016.9.24 4 #include <iostream> 5 #include <cstring> 6 #include <iomanip> 7 #include <cstdio> 8 #include <cstdlib> 9 #include <string>10 #include <algorithm>11 #include <queue>12 #include <map>13 #include <ctime>14 #include <cmath>15 using namespace std;16 #define ll long long17 #define up(i,j,n)        for(int i=j;i<=n;i++)18 #define down(i,j,n)        for(int i=j;i>=n;i--)19 #define FILE "gcd"20 const ll MAXN=1e6+5;21 const ll oo=0x3f3f3f3f;22 const ll mod=1LL<<31;23 inline ll read(){24     char ch=getchar();ll x=0,f=1;25     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}26     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}27     return x*f;28 }29 ll N,g[MAXN],c[MAXN],d[MAXN],gcd[MAXN],cd[MAXN],gc[MAXN],M,ans;30 char s[MAXN];31 namespace solution{32     void init(){33         scanf("%s",s+1);34         N=strlen(s+1);35     }36     void pret(){37         memset(g,0,sizeof(g));memset(c,0,sizeof(c));memset(d,0,sizeof(d));38         memset(gc,0,sizeof(gc));memset(cd,0,sizeof(cd));memset(gcd,0,sizeof(gcd));39         down(i,N,1){40             g[i]=g[i+1]+(s[i]==‘g‘?1:0);41             c[i]=c[i+1]+(s[i]==‘c‘?1:0);42             d[i]=d[i+1]+(s[i]==‘d‘?1:0);43         }44         down(i,N,1){45             cd[i]=(cd[i+1]+(s[i]==‘c‘?d[i]:0))%mod;46             gc[i]=(gc[i+1]+(s[i]==‘g‘?c[i]:0))%mod;47         }48         down(i,N,1)gcd[i]=(gcd[i+1]+(s[i]==‘g‘?cd[i]:0))%mod;49     }50     void slove(){51         M=read();52         while(M--){53             ll leftt=read(),rightt=read();54             if(leftt>rightt)swap(leftt,rightt);55             ans=(gcd[leftt]-gcd[rightt+1]+mod)%mod;56             ll tmp_gc=(gc[leftt]-gc[rightt+1]+mod)%mod;57             tmp_gc=(tmp_gc-((g[leftt]-g[rightt+1])*c[rightt+1])%mod+mod)%mod;58             ans=(ans-(tmp_gc*d[rightt+1])%mod+mod)%mod;59             ans=(ans-((g[leftt]-g[rightt+1])*cd[rightt+1])%mod+mod)%mod;60             printf("%d\n",(int)ans);61         }62     }63 }64 int main(){65     freopen(FILE".in","r",stdin);66     freopen(FILE".out","w",stdout);67     using namespace solution;68     init();69     pret();70     slove();71     return 0;72 }

  1 //NOIp 0924 pod  2 //by Cydiater  3 //2016.9.24  4 #include <iostream>  5 #include <cstring>  6 #include <cstdlib>  7 #include <cstdio>  8 #include <queue>  9 #include <map> 10 #include <ctime> 11 #include <cmath> 12 #include <iomanip> 13 #include <algorithm> 14 #include <string> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)        for(int i=j;i<=n;i++) 18 #define down(i,j,n)        for(int i=j;i>=n;i--) 19 #define FILE "pod" 20 const int MAXN=1e6+5; 21 const int oo=0x3f3f3f3f; 22 inline int read(){ 23     char ch=getchar();int x=0,f=1; 24     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 25     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 26     return x*f; 27 } 28 int N,M,Q,LINK[MAXN],len=0,f[MAXN],f2[MAXN],tol[MAXN]; 29 struct edge{ 30     int x,y,next,v; 31 }e[MAXN<<1]; 32 bool OK[MAXN]; 33 namespace solution{ 34     inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;e[len].x=x;} 35     int gcd(int a,int b){return b==0?a:gcd(b,a%b);} 36     int getf(int k){ 37         if(f[k]==k)        return k; 38         f[k]=getf(f[k]); 39         return f[k]; 40     } 41     int getf2(int k){ 42         if(f2[k]==k)        return k; 43         f2[k]=getf2(f2[k]); 44         return f2[k]; 45     } 46     void merge(int x,int y,int v){ 47         x=getf(x);y=getf(y); 48         if(tol[x]!=0)v=gcd(v,tol[x]); 49         if(tol[y]!=0)v=gcd(v,tol[y]); 50         tol[x]=v;f[y]=x; 51     } 52     int merge2(int x,int y,int v){ 53         if(v==1){ 54             if(getf2(x)==getf2(y))        return 0; 55             f2[getf2(x)]=getf2(y+N); 56             f2[getf2(y)]=getf2(x+N); 57         }else{ 58             if(getf2(x)==getf2(y+N))    return 0; 59             f2[getf2(x)]=getf2(y); 60             f2[getf2(x+N)]=getf2(y+N); 61         } 62         return 1; 63     } 64     void init(){ 65         N=read();M=read();Q=read(); 66         memset(tol,0,sizeof(tol)); 67         up(i,1,N){ 68             f[i]=i;f2[i]=i; 69             f2[i+N]=i+N; 70         } 71         up(i,1,M){ 72             int x=read(),y=read(),v=read(); 73             insert(x,y,v);insert(y,x,v); 74             merge(x,y,v); 75         } 76         up(i,1,M<<1){ 77             int x=e[i].x,y=e[i].y,v=e[i].v; 78             int d=tol[getf(e[i].x)]; 79             int flag=merge2(x,y,(v/d)%2); 80             if(!flag)OK[getf(x)]=1; 81             i+=1; 82         } 83     } 84     void slove(){ 85         while(Q--){ 86             int x=read(),y=read(),K=read(); 87             if(getf(x)!=getf(y))        puts("NIE");//unconnect 88             else{ 89                 int d=gcd(K,tol[getf(x)]); 90                 if((K/d)&1)                            puts("0"); 91                 else{ 92                     if(OK[getf(x)])                    puts("0"); 93                     else{ 94                         if(getf2(x)==getf2(y))        puts("0");//same color 95                         else                          printf("%d\n",d); 96                     } 97                 } 98             } 99         }100     }101 }102 int main(){103     freopen(FILE".in","r",stdin);104     freopen(FILE".out","w",stdout);105     using namespace solution;106     init();107     slove();108     return 0;109 }