結果
問題 | No.176 2種類の切手 |
ユーザー |
![]() |
提出日時 | 2016-10-04 18:17:38 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,406 bytes |
コンパイル時間 | 586 ms |
コンパイル使用メモリ | 75,544 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-21 15:56:12 |
合計ジャッジ時間 | 1,458 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 7 WA * 22 |
ソースコード
#include <iostream> #include <algorithm> #include <map> #include <vector> #include <cmath> using namespace std; int main() { int a, b, t; cin >> a >> b >> t; if (a > b)swap(a, b); vector<pair<int, int> > soinsu[2]; int i = 2; while (a >= i*i){ if (a%i == 0){ int cnt = 0; while (a%i == 0){ a /= i; cnt++; } soinsu[0].push_back(make_pair(i, cnt)); } else{ i++; } } soinsu[0].push_back(make_pair(a, 1)); i = 2; while (b >= i*i){ if (b%i == 0){ int cnt = 0; while (b%i == 0){ b /= i; cnt++; } soinsu[1].push_back(make_pair(i, cnt)); } else{ i++; } } soinsu[1].push_back(make_pair(b, 1)); int gcd = 1; vector<pair<int,int> >g; for (i = 0; i < soinsu[0].size();i++){ g.push_back(make_pair(soinsu[0][i].first,soinsu[0][i].second)); } for (int j = 0; j < soinsu[1].size(); j++){ for (i = 0; i < g.size(); i++){ if (soinsu[1][j].first == g[i].first){ g[i] = make_pair(g[i].first, max(g[i].second, soinsu[1][j].second)); break; } if (i == g.size() - 1)g.push_back(make_pair(soinsu[1][j].first, soinsu[1][j].second)); } } for (i = 0; i < g.size(); i++){ gcd *= pow(g[i].first, g[i].second); } //cout << gcd << endl; int t2 = t; t %= gcd; //cout << t << endl; int mn = 1000000001; int x; for (int i = 0; i*b <= t; i++){ mn = min(mn, (a - (t - i*b)%a)%a); } cout << mn + t2 << endl; return 0; }