考试

something-for-nothing 2021-09-01 原文

方程的解
【题目描述】
 给出一个二元一次方程 ax+by=c，其中 x、y 是未知数，求它的正整数解的
数量。
【输入格式】
 第一行一个整数 T，表示有 T 组数据。接下来 T 行，每行 3 个整数 a、b、c。
【输出格式】
 输出 T 行，每行一个数，表示方程解的数量。如果正整数解的数量比
65535 还多，输出“ZenMeZheMeDuo”。
【样例输入】
3
-1 -1 -3
1 1 65536
1 1 65537
【样例输出】
2
65535
ZenMeZheMeDuo
【数据规模与约定】
20%的数据，a=b=1
40%的数据，T≤100，1≤a,b,c≤1000
另 20%的数据，a+b=c，1≤a,b,c≤1,000,000
另 20%的数据，1≤a,b,c≤1,000,000
100%的数据，T≤10000，-1,000,000≤a,b,c≤1,000,000

　这有可能是noip前倒数第二场考试了

只是一道很简单的模拟题

求一下gcd然后进行特判即可

代码如下

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 inline ll read(){
 5     ll x=0;int f=1;char ch=getchar();
 6     while(!isdigit(ch)) {if(ch==\'-\') f=-1;ch=getchar();}
 7     while(isdigit(ch)) {x=x*10+ch-\'0\';ch=getchar();}
 8     return x*f;
 9 }
10 namespace solution{
11     ll a,b,c,x,y,T,k;
12     inline void extent_gcd(ll aa,ll bb){
13         if(bb==0){
14             x=1;y=0;k=aa;return;
15         }
16         extent_gcd(bb,aa%bb);
17         int t=x;
18         x=y;
19         y=t-aa/bb*y;
20     }
21     void init(){
22         T=read();
23     }
24     void solve(){
25         while(T--){
26             a=read();b=read();c=read();
27             if(a==0){
28                 if(c%b==0&&c/b>=0) cout<<1<<endl;
29                 else cout<<0<<endl;
30                 continue;
31             }
32             if(b==0){
33                 if(c%a==0&&c/a>=0) cout<<1<<endl;
34                 else cout<<0<<endl;
35                 continue;
36             }
37             if((a<=0&&b<=0&&c>=0)||(a>=0&&b>=0&c<=0)){
38                 if(a==0&&b==0&&c==0){
39                     printf("ZenMeZheMeDuo\n");
40                 }
41                 else printf("0\n");
42                 continue;
43             }
44             extent_gcd(a,b);
45             //cout<<a*x+b*y<<endl;
46             //cout<<k<<endl;
47             a/=k;b/=k;c/=k;
48             //cout<<a<<\' \'<<b<<\' \'<<c<<endl;
49             x*=c;y*=c;//cout<<x<<\' \'<<y<<endl;
50             int ta;
51             if(y<=0) ta=y/a-1,x+=ta*b,y=y%a+a;    
52             if(x<=0){
53                 printf("0\n");
54                 continue;
55             }
56             if(b>0&&a>0||b<0&&a<0){
57              if(x/abs(b)+1>65535) printf("ZenMeZheMeDuo\n");
58              else printf("%lld\n",x/abs(b)+1);
59              continue;
60             }
61             if((b>0&&a<0)||(a>0&&b<0)){
62                    printf("ZenMeZheMeDuo\n");
63                    continue;
64             }
65             //int minn=10000000;
66             //minn=min(minn,c/)
67         }
68     }
69 }
70 int main(){
71     //freopen("fuction.in","r",stdin);
72     //freopen("fuction.out","w",stdout);
73     using namespace solution;
74     init();
75     solve();
76     return 0;
77 }