結果

問題 No.1973 Divisor Sequence
ユーザー RiRinbaru
提出日時 2025-04-04 02:25:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,036 bytes
コンパイル時間 4,159 ms
コンパイル使用メモリ 238,452 KB
実行使用メモリ 40,484 KB
最終ジャッジ日時 2025-04-04 02:25:42
合計ジャッジ時間 8,332 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, p, n) for (ll i = p; i < (ll)(n); i++)
#define rep2(i, p, n) for (ll i = p; i >= (ll)(n); i--)
using namespace std;
using ll = long long;
using ld = long double;
const double pi = 3.141592653589793;
const long long inf = 2 * 1e9;
const long long linf = 4 * 1e18;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

// atcoder
#include <atcoder/all>
using namespace atcoder;
using mint1 = modint1000000007;
using mint2 = modint998244353;

vector<pair<ll, ll>> base = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 行列A, Bについて、A*Bを返す
vector<vector<ll>> prodMat(vector<vector<ll>> &A, vector<vector<ll>> &B, ll mod)
{
    ll N = A.size();
    ll P = A.at(0).size();
    ll M = B.at(0).size();
    vector<vector<ll>> res(N, vector<ll>(N));
    rep(i, 0, N)
    {
        rep(j, 0, M)
        {
            rep(k, 0, P)
            {
                res.at(i).at(j) += A.at(i).at(k) * B.at(k).at(j);
                res.at(i).at(j) %= mod;
            }
        }
    }
    return res;
}

// GのX乗
vector<vector<ll>> powMat(vector<vector<ll>> &G, ll X, ll mod)
{
    ll N = G.size();
    vector<vector<vector<ll>>> rui(61, vector<vector<ll>>(N, vector<ll>(N)));
    vector<vector<ll>> res(N, vector<ll>(N));
    rep(i, 0, N)
    {
        rep(j, 0, N)
        {
            rui.at(0).at(i).at(j) = G.at(i).at(j);
        }
    }
    rep(i, 1, 61)
    {
        rui.at(i) = prodMat(rui.at(i - 1), rui.at(i - 1), mod);
    }
    rep(i, 0, N)
    {
        res.at(i).at(i) = 1;
    }
    ll now = 1;
    rep(i, 0, 61)
    {
        if (now & X)
        {
            res = prodMat(res, rui.at(i), mod);
        }
        now *= 2;
    }
    return res;
}

int main()
{

    //////////////////
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //////////////////

    ll N, M;
    cin >> N >> M;
    set<ll> st;
    rep(i, 0, sqrt(M)) {
        if (M%(i+1)==0) {
            st.insert(i + 1);
        }
    }
    queue<ll> Q;
    for(ll c:st) {
        Q.push(M / c);
    }
    while(Q.size()) {
        st.insert(Q.front());
        Q.pop();
    }
    vector<ll> li;
    while(st.size()) {
        li.push_back(*begin(st));
        st.erase(*begin(st));
    }
    vector<vector<ll>> G(li.size(), vector<ll>(li.size()));
    rep(i, 0, li.size()) {
        rep(j, 0, li.size()) {
            if (M % li.at(i)==0 && (M / li.at(i)) % li.at(j) == 0) {
                G.at(i).at(j) = 1;
            }
            // cout << G.at(i).at(j) << " ";
        }
        // cout << endl;
    }
    auto ans=powMat(G, N - 1, mod1);
    mint1 temp=0;
    rep(i, 0, ans.size())
    {
        rep(j, 0, ans.size()) {
            temp += ans.at(i).at(j);
        }
    }
    cout << temp.val() << endl;
    return 0;
}
0