【题目描述】
给出一个二元一次方程 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
【题解】
核心为拓展欧几里得：
1、若a或b等于0看不为零的是否整除c 若c为0看a,b是否异号；
2、若两者为负就转化为一者为负；
3、若a,b异号，假设a<0,b>0则循环x至多b次；
4、若a,b同号但不与c同号，则方程无解 由此若a,b,c均为负就可以全部化为正；
以上为特殊情况，答案只可能是0或者无穷多。以下情况中，a,b,c均为正数。
5、枚举x，从1开始，满足c-ax>=0,寻找某一时刻(c-ax)%b==0,则找到了方程的一组解；
6、这一组解一定是x最小y最大的那组解，对于相邻的每两组解，y都减去了a和b的最小公倍数除以b，观察y能够减去多少个这个数；
再注意特判，注意处理负数情况即可。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
il int gi()
{
re int x=0;
re short int t=1;
re char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void exgcd(int a,int b,int c,long long &x,long long &y,int &d)//拓展欧几里得算法模板
{
if(!b) y=0,d=a,x=c/a;
else exgcd(b,a%b,c,y,x,d),y-=(a/b)*x;
}
void f()
{
int a,b,c,d;
ll x,y;
a=gi();b=gi();c=gi();
if(!a && !b)//特判a、b都等于0的情况
{
if(!c)
printf("ZenMeZheMeDuo
");
else
printf("0
");
return;
}
if(c<0) a=-a,b=-b,c=-c;
bool fana=0;
if(a<0) a=-a,fana=1;
bool fanb=0;
if(b<0) b=-b,fanb=1;//处理掉负数,有负数会WA
exgcd(a,b,c,x,y,d);//弄组解出来
if(a*x+b*y!=c)//一组解都没有就gg了
{
printf("0
");
return;
}
if(fana) x=-x,a=-a;
if(fanb) y=-y,b=-b;//把负数弄回来
if(a==0)
{
if(y<=0) printf("0
");
else printf("ZenMeZheMeDuo
");
return;
}
if(b==0)
{
if(x<=0) printf("0
");
else printf("ZenMeZheMeDuo
");
return;
}
if(a<0 && b>0 || a>0 && b<0)
{
printf("ZenMeZheMeDuo
");
return;
}//特判很重要
if(a<0) a=-a,b=-b,c=-c;
a/=d;b/=d;c/=d;//d是最大公约数
x%=b;
if(x<=0) x+=b;
if(x==0) x+=b;//保证模出的是正数
y=(c-a*x)/b;
ll miny=y%a;//求出y的最小值
if(miny<0) miny+=a;
if(miny==0) miny+=a;
int res;
if(miny>y) res=0;
else res=(y-miny)/a+1;//求出解的个数
if(res>65535) printf("ZenMeZheMeDuo
");
else printf("%d
",res);
}
int main()
{
freopen("fuction.in","r",stdin);
freopen("fuction.out","w",stdout);
int T;
T=gi();
while(T--)
f();
fclose(stdin);
fclose(stdout);
return 0;
}
顺便再记一下爆搜+剪枝的方法，虽然慢，但不容易打错。。。
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll T,a,b,c,neg;
ll gcd(ll x,ll y)
{
if (y==0) return x;
return gcd(y,x%y);
}
ll gi()
{
ll x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=-1,ch=getchar();
while (ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*w;
}
int main()
{
//freopen("fuction.in","r",stdin);
//freopen("fuction.out","w",stdout);
T=gi();
while (T--)
{
a=gi();b=gi();c=gi();neg=0;
if (a==0&&b==0&&c==0)
{
printf("ZenMeZheMeDuo
");
continue;
}
if (c==0)
{
if (a==0||b==0) printf("0
");
else if ((a<0&&b>0)||(a>0&&b<0)) printf("ZenMeZheMeDuo
");
else printf("0
");
continue;
}
if (a==0||b==0)
{
if (a==0&&b==0) printf("0
");
else
{
ll t=(a==0)?b:a;
if ((t>0&&c<0)||(t<0&&c>0)) printf("0
");
else
{
if (t<0) t=-t,c=-c;
if (c%t==0) printf("ZenMeZheMeDuo
");
else printf("0
");
}
}
continue;
}
if (a<0) neg++;
if (b<0) neg++;
if (c<0) neg++;
if (a>0&&b>0&&c>0&&a+b==c)
{
printf("1
");
continue;
}
if (neg>=2) a=-a,b=-b,c=-c,neg=3-neg;
if (neg==1)
{
if (c<0)
{
printf("0
");
continue;
}
if (a<0||b<0)
{
if (b<0) swap(a,b);
bool key=0;
for (ll x=1;x<=b;x++)
if ((c-a*x)%b==0)
{
key=1;break;
}
if (key==1) printf("ZenMeZheMeDuo
");
else printf("0
");
continue;
}
}
if (neg==0)
{
ll X,Y;
for (X=1;c-a*X>0;X++)
if ((c-a*X)%b==0) break;
if (c-a*X<=0) printf("0
");
else
{
Y=(c-a*X)/b;
ll num=a/gcd(a,b);
ll ans=Y/num+1;
if (Y%num==0) ans--;
if (ans>65535) printf("ZenMeZheMeDuo
");
else printf("%lld
",ans);
}
}
}
return 0;
}