結果

問題 No.1581 Multiple Sequence
ユーザー aperiodicmikanaperiodicmikan
提出日時 2021-07-02 22:57:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 244 ms / 2,000 ms
コード長 3,066 bytes
コンパイル時間 1,965 ms
コンパイル使用メモリ 177,044 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-29 12:50:23
合計ジャッジ時間 8,812 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 242 ms
5,248 KB
testcase_01 AC 242 ms
5,376 KB
testcase_02 AC 242 ms
5,376 KB
testcase_03 AC 243 ms
5,376 KB
testcase_04 AC 243 ms
5,376 KB
testcase_05 AC 242 ms
5,376 KB
testcase_06 AC 243 ms
5,376 KB
testcase_07 AC 243 ms
5,376 KB
testcase_08 AC 243 ms
5,376 KB
testcase_09 AC 243 ms
5,376 KB
testcase_10 AC 244 ms
5,376 KB
testcase_11 AC 243 ms
5,376 KB
testcase_12 AC 243 ms
5,376 KB
testcase_13 AC 242 ms
5,376 KB
testcase_14 AC 243 ms
5,376 KB
testcase_15 AC 243 ms
5,376 KB
testcase_16 AC 243 ms
5,376 KB
testcase_17 AC 244 ms
5,376 KB
testcase_18 AC 244 ms
5,376 KB
testcase_19 AC 243 ms
5,376 KB
testcase_20 AC 244 ms
5,376 KB
testcase_21 AC 242 ms
5,376 KB
testcase_22 AC 243 ms
5,376 KB
testcase_23 AC 243 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,begin, end) for (ll i = begin; i < (ll)(end); i++)

using namespace std;
using ll = long long;
template<typename T>
using pqueueAsc = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using pqueueDesc = priority_queue<T, vector<T>, less<T>>;

template<typename T>
using vec2 = vector<vector<T>>;
template<typename T>
using vec3 = vec2<vector<T>>;
template<typename T>
using vec4 = vec3<vector<T>>;
template<typename T>
using vec5 = vec4<vector<T>>;
template<typename T>
using vec6 = vec5<vector<T>>;

int gcd(int a, int b){
    if(b == 0)return a;
    return gcd(b, a%b);
}
ll extGCD(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll g = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return g;
}
//ax+by=cをみたす整数x,y
bool solveLinearEquation2(ll a, ll b, ll c, ll &x, ll &y){
    if(c % gcd(a,b) != 0)return false;
    /*
        (a/d)X+(b/d)Y=c/d
        (a/d)x+(b/d)y=1
        (a/d)(c/d)x+(b/d)(c/d)y=c/d
        X=(c/d)x-k(b/d)
        Y=(c/d)y+k(a/d)
        必要に応じてkを決める
    */
    ll d = extGCD(a,b,x,y);
    ll k = 0;
    x = (c/d)*x-k*(b/d);
    y = (c/d)*y+k*(a/d);
    
    return true;
}
ll MOD = 1000000007;

vector<ll> mfact(1,1);

ll minv(ll a){
    ll x;ll y;
    extGCD(a, MOD, x, y);
    if(x<0){
        x+= ((-x)/MOD+1)*MOD;
        x %= MOD;
    }
    return x;
}

ll mpow(ll a,ll b){
    ll res = 1;
    while(b > 0){
        if(b%2==1)res=(res*a)%MOD;
        b/=2;
        a = (a*a)%MOD;
    }
    return res;
}

ll mfactorial(ll a){
    if(mfact.size()-1 >= a)return mfact[a];
    for(ll i = mfact.size();i<=a;i++){
        mfact.push_back((i * mfact[i-1])%MOD);
    }
    return mfact[a];
}

ll mcomb(ll n, ll r){
    return (((mfactorial(n) * minv(mfactorial(r)))%MOD) * minv(mfactorial(n-r)))%MOD;
}
ll ipow(ll a, ll b){
    ll res = 1;
    while(b > 0){
        if(b % 2 == 1)res*=a;
        a*=a;
        b/=2;
    }
    return res;
}

void factorize(map<ll,ll>& fac, vector<ll>& sieved, ll a){
    while(a != 1){
        if(fac.find(sieved[a]) == fac.end())fac[sieved[a]] = 0;
        fac[sieved[a]]++;
        a/=sieved[a];

    }
}
/**
 * エラトステネスのふるい
 * res[i]はiの最小の素因数
 */
void primesieve(vector<ll>& res,ll n){
    res = vector<ll>(n+1, -1);
    for(int i = 2;i <= n;i++){
        if(res[i] != -1)continue;
        res[i] = i;
        for(int j = 2;j*i <= n;j++){
            res[j*i] = i;
        }
    }
}
/**
 * ふるい->素数だけ取り出す
 */
vector<ll> primesuntil(ll n){
    vector<ll> res;
    vector<ll> sieved;
    primesieve(sieved, n);
    for(int i = 2;i <= n;i++){
        if(sieved[i] == i)res.push_back(i);
    }
    return res;
}

int main(){
    ll M;cin>>M;
    vector<ll> dp(100001);
    dp[0] = 1;
    rep(i,1,100001){
        for(int j = 1;j * j <= i;j++){
            if(i%j != 0)continue;
            dp[i] += dp[i/j-1];
            if(j*j != i)dp[i] += dp[j-1];
            dp[i] %= MOD;
        }
    }
    cout<<dp[M]<<endl;
}
0