結果

問題 No.890 移調の限られた旋法
ユーザー trineutrontrineutron
提出日時 2019-06-24 21:19:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 215 ms / 2,000 ms
コード長 1,558 bytes
コンパイル時間 1,696 ms
コンパイル使用メモリ 171,440 KB
実行使用メモリ 19,160 KB
最終ジャッジ日時 2023-09-21 04:15:34
合計ジャッジ時間 6,467 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 215 ms
19,160 KB
testcase_14 AC 214 ms
18,852 KB
testcase_15 AC 214 ms
18,704 KB
testcase_16 AC 214 ms
19,052 KB
testcase_17 AC 195 ms
17,996 KB
testcase_18 AC 195 ms
17,780 KB
testcase_19 AC 118 ms
16,664 KB
testcase_20 AC 75 ms
10,644 KB
testcase_21 AC 17 ms
4,740 KB
testcase_22 AC 166 ms
17,516 KB
testcase_23 AC 202 ms
18,292 KB
testcase_24 AC 122 ms
17,188 KB
testcase_25 AC 29 ms
5,248 KB
testcase_26 AC 206 ms
18,080 KB
testcase_27 AC 210 ms
18,516 KB
testcase_28 AC 139 ms
17,512 KB
testcase_29 AC 91 ms
10,736 KB
testcase_30 AC 194 ms
17,916 KB
testcase_31 AC 111 ms
11,080 KB
testcase_32 AC 180 ms
17,764 KB
testcase_33 AC 191 ms
17,400 KB
testcase_34 AC 191 ms
18,004 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