湘潭市大学四月月赛C题A+B(扩展欧几里得定理)
湘潭大学四月月赛C题A+B(扩展欧几里得定理)
感谢cc_again......
A+B |
||
| Accepted : 8 | Submit : 77 | |
| Time Limit : 1000 MS | Memory Limit : 65536 KB | |
题目描述给你三个整数a，b，n。问有多少种只包含a，b的不同序列，使得这个序列的和为n。 例如a=2，b=3，n=7，那么有一种序列：(2+2+3=7，2+3+2=7，3+2+2=7)这三种看作相同，算一种。 例如a=3，b=3，n=6，那么只有一种序列：3+3=6。 例如a=4，b=5，n=7，那么不管a和b怎么排都不会等于7，那么就只有0种序列。 输入多个样例，每个样例占一行，包括3个整数a，b，n。(0< a,b,n <10^9).直到文件结束。 输出每个样例输出一行，一个整数，为a，b所能排出的序列数。 样例输入2 3 7 3 3 6 4 5 7 样例输出1 1 0 |
题目意思就不说了，中文题目。
看到这个就想到了扩展欧几里得，不过手搓，没写出来，然后就找了以前自己写的扩展欧几里得模板。
没学过扩展欧几里得算法的可以看下http://blog.sina.com.cn/s/blog_61c7e64d0100kwna.html 科普下。
利用扩展欧几里得可以解出ax+by=1的一个解，
现在的x,y是ax+by=1的一个解，
x=x*s,y=y*s; 同时扩大s倍，
现在的xy是ax+by=s的一个解。
现在的xy是ax+by=s的一个解。
因为ax+by=s，所以a(x+nb)+b(y-na)=s也是可行解。
进而可以把ax+by=s通解找到。
由于这个题目要使得解都是正数或0，（0也可以，这点是大坑。。。要不是晓东当时问了一句c题是不是a和b不一定要有，当时都不知道问题所在。）还有就是a==b需要特判。
AC代码：
//a和b不一定要有，fuck!!!
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
//不用int64就可以A的
__int64 exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
__int64 g=exgcd(b,a%b,x,y);
__int64 temp=x;
x=y;
y=temp-(a/b)*y;
return g;
}
__int64 gcd(__int64 m,__int64 n)
{
while(n)
{
__int64 tmp=m%n;
m=n;
n=tmp;
}
return m;
}
__int64 mi(__int64 m,__int64 n)
{
if(m>n) return n;
return m;
}
__int64 ma(__int64 m,__int64 n)
{
if(m>n) return m;
return n;
}
int main()
{
__int64 a,b,s,d;
while(~scanf("%I64d%I64d%I64d",&a,&b,&s))
{
__int64 x,y;
d=gcd(a,b);
if(s%d!=0)
{
puts("0");
continue;
}
else if(a+b>s)
{
puts("0");
continue;
}
else if(a==b)
{
if(s%a==0)
puts("1");
else puts("0");
continue;
}
a=a/d,b=b/d,s=s/d;
__int64 tt=exgcd(a,b,x,y);
//现在的x,y是ax+by=1的一个解
x=x*s,y=y*s;
//现在的xy是ax+by=s的一个解
__int64 cnt=0;
//__int64 s1,s2;
//根据x,y的值来判断到底有多少可行解
//因为ax+by=s，所以a(x+nb)+b(y-na)=s也是可行解，所以直接找n的值使得x+nb与y-na都为正数或0即可
//代码写搓了。。
/*if(x<=0&&y>=0) //okok
{
x=-x;
if(x%b==0) s1=x/b;
else s1=x/b+1;
if(y%a==0) s2=y/a;
else s2=y/a;
}
else if(y<=0&&x>=0) //okok
{
y=-y;
if(y%a==0) s1=y/a;
else s1=y/a+1;
if(x%b==0) s2=x/b;
else s2=x/b;
}
else if(x>0&&y>0) //ok
{
s1=-x/b;
s2=x/b;
s1=ma(s1,-y/a);
s2=mi(s2,y/a);
}
else
{
puts("0");
continue;
}*/
x=x%b;
if(x<0) x+=b;
y=(s-a*x)/b; //解出a(x+nb)+b(y-na)=s,n=0时候的值
if(y<0) cnt=0;
else cnt=y/a+1;
printf("%I64d\n",cnt);
}
return 0;
}
感谢cc_again......