結果

問題 No.890 移調の限られた旋法
ユーザー trineutrontrineutron
提出日時 2019-06-24 21:19:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 212 ms / 2,000 ms
コード長 1,558 bytes
コンパイル時間 1,593 ms
コンパイル使用メモリ 173,588 KB
実行使用メモリ 19,064 KB
最終ジャッジ日時 2024-07-06 22:52:22
合計ジャッジ時間 5,860 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 207 ms
19,032 KB
testcase_14 AC 212 ms
19,032 KB
testcase_15 AC 210 ms
19,064 KB
testcase_16 AC 208 ms
19,032 KB
testcase_17 AC 183 ms
17,364 KB
testcase_18 AC 188 ms
17,496 KB
testcase_19 AC 116 ms
15,700 KB
testcase_20 AC 73 ms
9,560 KB
testcase_21 AC 18 ms
5,376 KB
testcase_22 AC 163 ms
15,700 KB
testcase_23 AC 200 ms
18,116 KB
testcase_24 AC 115 ms
15,704 KB
testcase_25 AC 28 ms
5,376 KB
testcase_26 AC 194 ms
18,388 KB
testcase_27 AC 198 ms
18,604 KB
testcase_28 AC 132 ms
15,828 KB
testcase_29 AC 86 ms
9,684 KB
testcase_30 AC 185 ms
17,600 KB
testcase_31 AC 108 ms
11,348 KB
testcase_32 AC 175 ms
16,344 KB
testcase_33 AC 180 ms
17,112 KB
testcase_34 AC 184 ms
17,112 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const long mod = 1000000007;
vector<long> fact, invfact;

void getprimes(vector<int> &primes, int g) {
    if (g % 2 == 0) primes.push_back(2);
    while (g % 2 == 0) g /= 2;
    if (g % 3 == 0) primes.push_back(3);
    while (g % 3 == 0) g /= 3;
    int d = 2, div = 5;
    while (div * div <= g) {
	if (g % div == 0) primes.push_back(div);
	while (g % div == 0) g /= div;
	div += d;
	d = 6 - d;
    }
    if (g > 1) primes.push_back(g);
}

int gcd(int m, int n) {
    if (n == 0) return m;
    return gcd(n, m % n);
}

long combination(int n, int k) {
    return (fact.at(n) * invfact.at(k) % mod) * invfact.at(n - k) % mod;
}

long power(long n, long i) {
    if (i == 0) return 1;
    long next = power(n * n % mod, i / 2);
    if (i % 2 == 0) return next;
    return n * next % mod;
}

long inv(long n) {
    return power(n, mod - 2);
}

void init_fact(int n) {
    fact.push_back(1);
    invfact.push_back(1);
    for (int i = 1; i <= n; i++) {
	fact.push_back(fact.at(i - 1) * i % mod);
	invfact.push_back(inv(fact.at(i)));
    }
}

int main()
{
    int n, k;
    cin >> n >> k;
    
    vector<int> primes;
    getprimes(primes, gcd(n, k));

    init_fact(n);
    
    long s = 0;
    for (int i = 1; i < 1 << primes.size(); i++) {
	int d = 1, count1s = 0;
	for (size_t j = 0; j < primes.size(); j++) {
	    if ((i >> j) % 2 == 1) {
		d *= primes.at(j);
		count1s++;
	    }
	}
	s += (2 * (count1s % 2) - 1) * combination(n / d, k / d);
	while (s < 0) s += mod;
	s %= mod;
    }
    cout << s << endl;
}
0