文章目录
A+B |
||
题目描述给你三个整数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
SourceWW |
代码：
/**
* 简单扩展欧几里得算法题
* （注）扩展欧几里得算法原理：
* x * a+y * b = Gcd(a, b) = Gcd(b,a%b)
* = _x * b + _y * a % b
* = _x * b +_y * (a – a / b * b)
* = _y * a + (_x – _y *a / b) * b
* 所以： x = _y y = _x – _y *a / b
*
* 本题思路：利用欧几里得算法求出一组解（x1,y1）
* 通解形式为(x1+k*b, y1-k*a), k为任意整数
* x1=x*n/g y1=y*n/g 再通过对a,b,n同时除以g求得x最小整数解
*/
#include <stdio.h>
#define ll __int64
ll x, y, g;
void ext_gcd(ll a, ll b)
{
if (b == 0){
x = 1;
y = 0;
g = a;
}
else{
ext_gcd(b, a%b);
ll temp = x;
x = y;
y = temp - a / b*y;
}
}
int main()
{
ll a, b, n;
while (scanf("%I64d%I64d%I64d", &a, &b, &n) != EOF)
{
if (a == b){
if (0 == n%a)
printf("1\n");
else
printf("0\n");
continue;
}
ext_gcd(a, b);
if (0 != n%g){
printf("0\n");
continue;
}
x = x*n / g; //求得x的一个解
a /= g;
b /= g;
n /= g;
x = x%b; // 因为x的通解为 x+k*b,所以x的最小整数解为x%b
if (x < 0)
x += b;
y = (n - a*x) / b; // 根据公式 a*x + b*y = n
if (y < 0){
printf("0\n");
continue;
}
ll k = (n / a - x) / b + 1; // x为最小整数解，a*(x+k*b)<=n 故 k=（n/a - x）/ b + 当k等于0
printf("%I64d\n", k);
}
return 0;
}