[CSP-S模拟测试]:方程的解（小学奥数）

题目描述

给出一个二元一次方程$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 \leqslant 100,1 \leqslant a,b,c \leqslant 1000$。
另$20\%$的数据，$a+b=c,1 \leqslant a,b,c \leqslant 1,000,000$。
另$20\%$的数据，$1 \leqslant a,b,c \leqslant 1,000,000$。
100%的数据，$T \leqslant 10,000,-1,000,000 \leqslant a,b,c \leqslant 1,000,000$。

题解

$20\%$算法：

对于$a=b=1$，那么解的个数为$\max(c-1,0)$，直接输出就好了。

$40\%$算法：

对于$1 \leqslant a,b,c \leqslant 1000$的数据，只需要暴力枚举$x$，$y$即可。

另$20\%$算法$1$：

对于$a+b=c$，直接输出$1$即可。

另$20\%$算法$2$：

考虑小学奥数知识，我们只需要暴力求出$x$或$y$的最小正整数解，然后每次加上$a$和$b$的$lcm$，看在$c$以内可以加多少次即可。

不过正解好像是扩展欧几里得，考场上的我并不会……

$100\%$算法：

其实是特判：

　　$1.$如果$a,b$异号，如果$c \mod gcd(a,b)=0$，那么会有无穷多的解，否则无解。

　　$2.$如果$a,b$同号但与$c$异号，那么无解。

　　$3.$如果$a$或$b$等于$0$，如果$c$可以整除$b$且$b$为正整数，那么会有无穷多解，否则无解。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int a,b,c;

int ans;

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d%d",&a,&b,&c);

		if(c<0)a=-a,b=-b,c=-c;//方便处理

		if((long long)a*b<0LL)//a,b异号，注意开long long，否则会爆

		{

			if(c%__gcd(a,b))puts("0");

			else puts("ZenMeZheMeDuo");

			continue;

		}

		if(a<0&&b<0)//a,b同号但与c异号

		{

			puts("0");

			continue;

		}

		if(!a)//为0的情况

		{

			if(c%b||c/b<0)puts("0");

			else puts("ZenMeZheMeDuo");

			continue;

		}

		if(!b)

		{

			if(c%a||c/a<0)puts("0");

			else puts("ZenMeZheMeDuo");

			continue;

		}

		if(a+b==c)

		{

			puts("1");

			continue;

		}

		int biu=c;

		int lcm=a*b/__gcd(a,b);

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

			if(!((c-i)%b)){biu=i;break;}

		if(biu==c){puts("0");continue;}//无解

		ans=(c-biu)/lcm;

		if((c-biu)%lcm)ans++;

		if(ans>65535)puts("ZenMeZheMeDuo");//判断解的个数

		else printf("%d\n",ans);

	}

	return 0;

}

rp++

巴特西