gcd，lcm，ext_gcd，inv

showproblem.php?pid=1019

 1 #include<cstdio>
 2 int gcd(int a,int b){
 3     return b?gcd(b,a%b):a;
 4 }
 5 int lcm(int a,int b){
 6     return a/gcd(a,b)*b;
 7 }
 8 int main(){
 9     int n,m,ans,x;
10     while(~scanf("%d",&n)){
11         while(n--){
12             ans=1;
13             scanf("%d",&m);
14             while(m--){
15                 scanf("%d",&x);
16                 ans=lcm(ans,x);
17             }
18             printf("%d
",ans);
19         }
20     }
21     return 0;
22 }

View Code

Turn the pokers http://acm.hdu.edu.cn/showproblem.php?pid=4869

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef __int64 LL;
 5 const int M=100010;
 6 const int mod=1000000009;
 7 int ext_gcd(int a,int b,int &x,int &y){//扩展gcd d=gcd(a,b)=a*x+b*y; return d,x,y;
 8     int t,ret;
 9     if(!b){
10         x=1;
11         y=0;
12         return a;
13     }
14     ret=ext_gcd(b,a%b,x,y);
15     t=x;
16     x=y;
17     y=t-a/b*y;
18     return ret;
19 }
20 int inv(int a,int b,int c){//ext_gcd求逆元 (b/a)%c
21     int x,y;
22     ext_gcd(a,c,x,y);
23     return (1LL*x*b%c+c)%c;
24 }
25 LL C[M];
26 LL INV[M];
27 int main() {
28     for(int i=1; i<M; i++) {
29         INV[i]=inv(i,1,mod);
30     }
31     int n,m,a;
32     while(~scanf("%d%d",&n,&m)) {
33         C[0]=1;
34         for(int i=1;i<=m;i++){
35             C[i]=C[i-1]*(m-i+1)%mod*INV[i]%mod;
36         }
37         int L=0,R=0,nl,nr,tmp;
38         for(int i=0;i<n;i++){
39             scanf("%d",&a);
40             tmp=min(m-L,a);
41             nr=L+tmp-(a-tmp);
42             tmp=min(R,a);
43             nl=R-tmp+(a-tmp);
44             if(nl>nr) swap(nl,nr);
45             if(L<=a&&a<=R){
46                 if(L%2==a%2){
47                     nl=0;
48                 }
49                 else{
50                     nl=min(nl,1);
51                 }
52             }
53             if((m-R)<=a&&a<=(m-L)){
54                 if((m-L)%2==a%2){
55                     nr=m;
56                 }
57                 else{
58                     nr=max(nr,m-1);
59                 }
60             }
61             if(L>=a) nl=min(nl,L-a);
62             if(m-R>=a) nr=max(nr,R+a);
63             L=nl;
64             R=nr;
65         }
66         int ans=0;
67         for(int i=L;i<=R;i+=2){
68             ans+=C[i];
69             ans%=mod;
70         }
71         printf("%d
",ans);
72     }
73     return 0;
74 }

View Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef __int64 LL;
 5 const int M=100010;
 6 const int mod=1000000009;
 7 LL C[M];
 8 LL INV[M];
 9 void inv_init(){//初始化%mod的乘法逆元
10     INV[1]=1;
11     for(int i=2;i<M;i++){
12         INV[i]=INV[mod%i]*(mod-mod/i)%mod;
13     }
14 }
15 int main() {
16     inv_init();
17     int n,m,a;
18     while(~scanf("%d%d",&n,&m)) {
19         C[0]=1;
20         for(int i=1;i<=m;i++){
21             C[i]=C[i-1]*(m-i+1)%mod*INV[i]%mod;
22         }
23         int L=0,R=0,nl,nr,tmp;
24         for(int i=0;i<n;i++){
25             scanf("%d",&a);
26             tmp=min(m-L,a);
27             nr=L+tmp-(a-tmp);
28             tmp=min(R,a);
29             nl=R-tmp+(a-tmp);
30             if(nl>nr) swap(nl,nr);
31             if(L<=a&&a<=R){
32                 if(L%2==a%2){
33                     nl=0;
34                 }
35                 else{
36                     nl=min(nl,1);
37                 }
38             }
39             if((m-R)<=a&&a<=(m-L)){
40                 if((m-L)%2==a%2){
41                     nr=m;
42                 }
43                 else{
44                     nr=max(nr,m-1);
45                 }
46             }
47             if(L>=a) nl=min(nl,L-a);
48             if(m-R>=a) nr=max(nr,R+a);
49             L=nl;
50             R=nr;
51         }
52         int ans=0;
53         for(int i=L;i<=R;i+=2){
54             ans+=C[i];
55             ans%=mod;
56         }
57         printf("%d
",ans);
58     }
59     return 0;
60 }

View Code

end