結果

問題 No.1973 Divisor Sequence
コンテスト
ユーザー 回転
提出日時 2025-10-23 16:35:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,588 bytes
コンパイル時間 3,215 ms
コンパイル使用メモリ 284,900 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-23 16:35:43
合計ジャッジ時間 11,838 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
MOD = 10**9+7
N,M = list(map(int,input().split()))

N,M = 5*10**5, 802241960520

def divisor(n):
    sq = n**0.5
    border = int(sq)
    table = []
    bigs = []
    for small in range(1, border+1):
        if n%small == 0:
            table.append(small)
            big = n//small
            bigs.append(big)
    if border == sq:#nが平方数
        bigs.pop()
    table += reversed(bigs)
    return table


ps = divisor(M)
print(len(ps))
exit()
dp = [[0 for _ in range(len(ps))] for _ in range(N)]
dp[0] = [1] * len(ps)

for i in range(N-1):
	for j in range(len(ps)):
		
		for k in range(len(ps)):
			if(ps[j] * ps[k] > M):break
			if(M % (ps[j]*ps[k]) != 0):continue
			dp[i+1][k] += dp[i][j]
			dp[i+1][k] %= MOD
		

print(sum(dp[-1]) % MOD)
*/
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 MOD = 1000000007LL;

vector<int64> divisors_sorted(int64 n) {
    vector<int64> smalls, bigs;
    int64 sq = floor(sqrt((long double)n));
    for (int64 s = 1; s <= sq; ++s) {
        if (n % s == 0) {
            smalls.push_back(s);
            int64 b = n / s;
            if (b != s) bigs.push_back(b);
        }
    }
    // smalls is increasing, bigs is decreasing (because we collected bigs in increasing s),
    // but we want full sorted ascending list:
    reverse(bigs.begin(), bigs.end()); // now bigs is ascending
    smalls.insert(smalls.end(), bigs.begin(), bigs.end());
    return smalls;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    int64 M;
    if (!(cin >> N >> M)) return 0;
    
    vector<int64> ps = divisors_sorted(M);
    int P = (int)ps.size();
    // rolling DP arrays
    vector<int64> cur(P, 1), nxt(P, 0); // dp[0] = all ones

    for (int i = 0; i < N - 1; ++i) {
        fill(nxt.begin(), nxt.end(), 0);
        for (int j = 0; j < P; ++j) {
            if (cur[j] == 0) continue;
            for (int k = 0; k < P; ++k) {
                // since ps is sorted ascending, can break when product > M
                // but check product might overflow if ps large; use __int128 to be safe
                __int128 prod = (__int128)ps[j] * (__int128)ps[k];
                if (prod > M) break;
                if (M % (ps[j] * ps[k]) != 0) continue;
                nxt[k] += cur[j];
                if (nxt[k] >= MOD) nxt[k] -= MOD * (nxt[k] / MOD);
            }
        }
        cur.swap(nxt);
    }

    int64 ans = 0;
    for (int i = 0; i < P; ++i) {
        ans += cur[i];
        if (ans >= MOD) ans -= MOD;
    }
    cout << (ans % MOD) << "\n";
    return 0;
}
0