結果

問題 No.982 Add
コンテスト
ユーザー kappybar
提出日時 2020-03-25 09:00:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,058 bytes
コンパイル時間 1,401 ms
コンパイル使用メモリ 163,564 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-01 19:51:06
合計ジャッジ時間 2,598 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;

int gcd(int i,int j){
        if(j == 0) return i;
        else return gcd(j,i%j);
}

 
int main() {
        int a,b;
        cin >> a >> b;
        if(gcd(a,b) != 1){
                cout << -1 << endl;
                return 0;
        }
        
        if(a > b) swap(a,b);
        vector<bool> dp(100000,0);
        dp[0] = 1;
        int res = 0,ans = 0;
        for(int i=1;i<100000;i++){
                if(i-a >= 0){
                        if(dp[i-a]) dp[i] = 1;
                }
                if(i-b >= 0){
                        if(dp[i-b]) dp[i] = 1;
                }
                if(dp[i]){
                        res ++;
                        if(res == a) break;
                }
                else{
                        ans ++;
                        res = 0;
                }
        }

        cout << ans << endl;


        return 0;
}
0