xjtoj-22-wmq的等式-扩展欧几里得

题目链接

最近好忙啊……先是建模把命建没了半条……又是科协收各种东西……今天实变函数和数学建模都结课了……然而还什么都不会……结完课马上就要考试……可以跳明远湖了……

题意：给定非负整数a,b,c,n(a,b,c<=2e5,n<=1e18),问是否存在非负整数x,y,z是的ax+by+cz=n成立

xjtu校赛的题目……真的好惨啊……一个半小时之后就开始咸鱼……明明后面有几题很简单的……还是自己太水了……这题赛场上没想到trick，xjb写了好久……赛后李主席告诉真相后我眼泪掉下来……

思路：考虑ax+by=n，这就是个扩展欧几里得模板题，看一下x取最小非负数时y是不是大于零就行了。关键是现在有个c，这个c怎么办呢？最简单的想法是枚举z，ax+by=n-cz；但是z的范围又太大了。设a,b,c按大小顺序排列，考虑当z>a时，z=a+p，这样ac部分就可以算进ax了，所以z的枚举范围只要0~min(n/c,a)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
long long INF=0x3f3f3f3f3f3f3f; 
long long gcd(long long a,long long b)
{
	if(b==0)return a;
	 else return gcd(b,a%b);
}
long long exgcd(long long a, long long b, long long &x, long long &y)
{  
    if (!b) {x = 1; y = 0; return a;}  
    long long d = exgcd(b, a % b, y, x);  
    y -= a / b * x;  
    return d;  
}   
 
 
int fangcheng(long long a,long long b,long long c,long long &x,long long &y)
{
    long long d=exgcd(a,b,x,y);
    if(c%d)
        return 0;
    int k=c/d;
    x*=k; y*=k;
	long long t=b/d;
	if(t<0)t=-t;
	x=(x%t+t)%t;
	y=(c-(x*a))/b;
	//printf("fangcheng : a=%lld,b=%lld,c=%lld jiex:%lld jiey:%lld\n",a,b,c,x,y);   
    return 1;
} 
int main()
{
	int t;
	long long a,b,c,d,n,aa,bb,cc;
	int kase=0;
	while(~scanf("%lld%lld%lld%lld",&aa,&bb,&cc,&n))
	{
		kase++;
		printf("Case #%d: ",kase);
		a=min(aa,min(bb,cc));
		c=max(aa,max(bb,cc));
		b=aa+bb+cc-a-c;
		long long r=min(a,n/c);
		long long x,y;
		int flag=0;
		for(int i=0;i<=r;i++)
		{
			long long d=n-(long long)c*i;
			if(fangcheng(a,b,d,x,y))
			{
				if(x>=0 && y>=0)
				{
				 flag=1;
				 break;
				}
			}
		}
		if(flag)printf("Yes\n");
		 else printf("No\n");
	}
	return 0;
 }