记录编号	283525	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-07-14 20:35:47	内存使用	0.34 MiB

#include "cstdio"
typedef long long ULL;

ULL Exgcd(ULL a, ULL b, ULL& d, ULL&x, ULL&y)//求 ax + by = d, |x| + |y|最小, 要求d = gcd(a, b) 
{
	if(!b){
		d = a; x = 1; y = 0;
	}
	else{
		Exgcd(b, a%b, d, y, x);
		y -= x*(a/b);
	}
}

ULL gcd(ULL a, ULL b)//求a, b最小公约数
{
	return b == 0 ? a : gcd(b, a%b);
}

bool vis[10100];
void Prime(int n)//找素数 
{
	for(int i = 2; i <= n; i++){
		if(!vis[i]){
			for(int j = i*i; j <= n; j += i)
				vis[j] = 1;
		}
	}
}

int phi[10100];
void Getphi(int n)//欧拉函数表, phi[i]表示不超过i且与i互素的整数个数, 类似筛法 
{
	phi[1] = 1;
	for(int i = 2; i <= n; i++){
		if(!phi[i]){
			for(int j = i; j <= n; j += i){
				if(!phi[j])	phi[j] = j;
				phi[j] = phi[j] / i * (i-1);
			}
		}
	}
}

ULL inv(ULL a, ULL n)//计算模n下a的乘法逆元, 无解则返回-1 
{
	ULL d, x, y;
	Exgcd(a, n, d, x, y);
	return d == 1 ? (x+n)%n : -1;
}

int main()
{
	freopen("HanXin.in", "r", stdin); freopen("HanXin.out", "w", stdout);
	ULL p[20] = {0}, a[20] = {0};
	ULL N, M, M2 = 1, Mi, ans = 0;
	scanf("%llu%llu", &N, &M);
	for(int i = 1; i <= M; i++){
		scanf("%llu%llu", &p[i], &a[i]);
		M2 *= p[i];
	}	
	for(int i = 1; i <= M; i++){
		Mi = M2 / p[i];
		ULL x = 0, y = 0, d = 1;
		Exgcd(Mi, p[i], d, x, y);
		ans += (a[i]*x*Mi + M2) % M2;//防止出现负数 
	}
	ans = (ans+M2) % M2;
	if(ans > N){
		puts("-1");
		return 0;
	}	
	while(ans < N)	ans += M2;//最大解 
	ans -= M2;
	printf("%llu", N-ans);
	return 0;	
}