51nod 1352 集合计数 （扩展欧几里得）

给出N个固定集合{1，N},{2,N-1},{3,N-2},...,{N-1,2},{N,1}.求出有多少个集合满足：第一个元素是A的倍数且第二个元素是B的倍数。

提示：

对于第二组测试数据，集合分别是：{1,10},{2,9},{3,8},{4,7},{5,6},{6,5},{7,4},{8,3},{9,2},{10,1}.满足条件的是第2个和第8个。

Input

第1行：1个整数T（1<=T<=50000)，表示有多少组测试数据。
第2 - T+1行：每行三个整数N，A,B（1<=N，A，B<=2147483647)

Output

对于每组测试数据输出一个数表示满足条件的集合的数量，占一行。

Input示例

2
5 2 4
10 2 3

Output示例

1
2

#include <iostream>
#include <vector>
#include <algorithm>
#include<stdio.h>
using namespace std;

long long N,A,B,result,d,z,xx,yy;

void ex_gcd(long long a,long long b,long long &xx,long long &yy)
{
	if(b==0)
	{
		xx=1;
		yy=0;
		d=a;
	}
	else
	{
		ex_gcd(b,a%b,xx,yy);

		long long t=xx;
		xx=yy;
		yy=t-(a/b)*yy;
	}
}

long long cal2()
{	
	result=0;
	ex_gcd(A,B,xx,yy);
	z=A*B/d;   //最小公倍数 

	if((1+N)%d)    //不存在整数解 
		return 0;
	else
	{
		xx=xx*((1+N)/d);   // ax+by=c。。。x的值 
		long long r=B/d;   
		xx = (xx%r+r)%r;
		if(xx==0)
			xx+=r;         // x的最小整数数解 
		long long remain=N-(xx)*A;
		if(remain<0)
			return 0;
		else
		{
			result++;
			result += remain/z;
		}
	}
	return result;
}
int main()
{
	int count;
	scanf("%d",&count);
	while(count--)
	{
		scanf("%lld%lld%lld",&N,&A,&B);
		printf("%lld\n",cal2());
	}
	return 0;
}

扩展欧几里得算法：

void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
	if(!b) {
		d=a;
		x=1;
		y=0;
	}
	else {
		ex_gcd(b,a%b,d,y,x);
		y-=x*(a/b);
	}
}