結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー htnglsh
提出日時 2018-11-25 22:23:03
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 225 ms / 3,000 ms
コード長 2,471 bytes
コンパイル時間 452 ms
コンパイル使用メモリ 32,000 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-25 21:10:03
合計ジャッジ時間 4,744 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#define int long long

int gcd(int a, int b){
	if(b == 0){
		return a;
	}
	else{
		return gcd(b, a % b);
	}
}

int lcm(int a, int b){
	return (a / gcd(a, b)) * b;
}

int MOD_m(int a, int m){
	a %= m;
	return a >= 0 ? a : a + m;
}

typedef struct {
	int s;
	int t;
}pair;
 
//拡張ユークリッドの互除法
//ax + by = gcd(x, y) となる(a, b)を求める
//x > 0, y >= 0 を仮定している
pair Extension_Euclidean(int x, int y){
	if(y == 0){
		return (pair){1, 0};
	}
	else{
		pair p = Extension_Euclidean(y, x % y);
		return (pair){p.t, p.s - p.t * (x / y)};
	}
}

//mod mでのaの逆元を求める
int inverse_m(int a, int m){
	if(gcd(a, m) > 1){
		return -1;
	}
	else{
		return MOD_m(Extension_Euclidean(a, m).s, m);
	}
}

//連立合同式を解くGarnerのアルゴリズム
//m[i] > 0 の時
//x = a[i] mod m[i] (i = 1,...,N)
//を満たす (x mod lcm(m[1],...,m[N])) mod M を求める
//存在しないときは-1を返す
int Garner(int *_a, int *_m, int N, int M){
	int i, j, f = 1;
	int *a = (int *)malloc(sizeof(int) * N);
	int *m = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		a[i] = _a[i] % _m[i];
		m[i] = _m[i];
		if(a[i] > 0){
			f = 0;
		}
	}
	int g, gi, gj;
	for(i = 0; i < N; i++){
		for(j = i + 1; j < N; j++){
			g = gcd(m[i], m[j]);
			if(MOD_m(a[i] - a[j], g) != 0){
				//解なし
				return -1;
			}
			m[i] /= g;
			m[j] /= g;
			gi = gcd(m[i], g);
			gj = g / gi;
			for(g = gcd(gi, gj); g > 1; g = gcd(gi, gj)){
				gi *= g;
				gj /= g;
			}
			m[i] *= gi;
			m[j] *= gj;
			a[i] = MOD_m(a[i], m[i]);
			a[j] = MOD_m(a[j], m[j]);
		}
	}
	//ここまでの処理により任意のi,jに対しm[i]とm[j]は互いに素になっている
	int T, ms, x;
	int *t = (int *)malloc(sizeof(int) * N);
	t[0] = a[0];
	for(i = 1; i < N; i++){
		T = 0;
		ms = 1;
		for(j = 0; j < i; j++){
			T = MOD_m(T + t[j] * ms, m[i]);
			ms = MOD_m(ms * m[j], m[i]);
		}
		t[i] = MOD_m((a[i] - T) * inverse_m(ms, m[i]), m[i]);
	}
	x = 0;
	ms = 1;
	for(i = 0; i < N; i++){
		x = MOD_m(x + t[i] * ms, M);
		ms = MOD_m(ms * m[i], M);
	}
	//ms = lcm(m[1],...,m[N]) mod M になっている
	if(f == 1){
		return ms;
	}
	else{
		return x;
	}
}

signed main(){
	int N, i;
	scanf("%lld", &N);
	int *X = (int *)malloc(sizeof(int) * N);
	int *Y = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%lld%lld", &X[i], &Y[i]);
	}
	printf("%lld\n", Garner(X, Y, N, (int)(1e9 + 7)));
	return 0;
}
0