結果

問題 No.3179 3 time mod
ユーザー Cafe1942
提出日時 2025-05-30 18:36:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 846 bytes
コンパイル時間 917 ms
コンパイル使用メモリ 68,952 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-30 20:10:38
合計ジャッジ時間 3,945 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using ll = long long;
using namespace std;

pair<ll, ll> func(ll a, ll b, ll c) {
	if (b == 0) {
		return { c / a,0 };
	}
	else {
		pair<ll, ll>tmp;
		tmp = func(b, a % b, c);
		return{ tmp.second,tmp.first - (a / b) * tmp.second };
	}
}

int main() {
	ll N;
	cin >> N;
	ll P, Q, R;
	cin >> P >> Q >> R;
	ll A, B, C;
	cin >> A >> B >> C;
	pair<ll, ll> tmp;
	tmp = func(P, Q, 1);
	ll good0 = ((__int128_t)A * (__int128_t)Q * (__int128_t)tmp.second + (__int128_t)B * (__int128_t)P * (__int128_t)tmp.first) % (__int128_t)(P * Q);
	tmp = func(P * Q, R, 1);
	ll good = ((__int128_t)good0 * R * (__int128_t)tmp.second + (__int128_t)C * (__int128_t)P * (__int128_t)Q * (__int128_t)tmp.first) % (__int128_t)(P * Q * R);
	if(N % (P * Q * R) < good){
	  cout << N / (P * Q * R);
	}
	else{
	  cout << N / (P * Q * R) + 1;
	}
	return 0;
}
0