結果

問題 No.890 移調の限られた旋法
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-09-20 22:45:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 3,780 bytes
コンパイル時間 8,527 ms
コンパイル使用メモリ 594,024 KB
実行使用メモリ 34,628 KB
最終ジャッジ日時 2024-09-14 18:50:52
合計ジャッジ時間 10,697 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
27,036 KB
testcase_01 AC 38 ms
26,896 KB
testcase_02 AC 40 ms
26,980 KB
testcase_03 AC 36 ms
26,992 KB
testcase_04 AC 39 ms
26,980 KB
testcase_05 AC 38 ms
27,024 KB
testcase_06 AC 38 ms
27,004 KB
testcase_07 AC 39 ms
26,880 KB
testcase_08 AC 39 ms
26,876 KB
testcase_09 AC 38 ms
26,980 KB
testcase_10 AC 38 ms
26,976 KB
testcase_11 AC 38 ms
27,072 KB
testcase_12 AC 39 ms
26,848 KB
testcase_13 AC 56 ms
34,628 KB
testcase_14 AC 56 ms
34,544 KB
testcase_15 AC 55 ms
34,576 KB
testcase_16 AC 56 ms
34,556 KB
testcase_17 AC 55 ms
33,772 KB
testcase_18 AC 58 ms
33,956 KB
testcase_19 AC 48 ms
30,920 KB
testcase_20 AC 44 ms
29,296 KB
testcase_21 AC 41 ms
27,264 KB
testcase_22 AC 54 ms
32,728 KB
testcase_23 AC 54 ms
34,076 KB
testcase_24 AC 48 ms
30,912 KB
testcase_25 AC 41 ms
27,804 KB
testcase_26 AC 54 ms
34,240 KB
testcase_27 AC 54 ms
34,416 KB
testcase_28 AC 50 ms
31,628 KB
testcase_29 AC 44 ms
29,784 KB
testcase_30 AC 57 ms
33,824 KB
testcase_31 AC 47 ms
30,804 KB
testcase_32 AC 59 ms
33,108 KB
testcase_33 AC 57 ms
33,644 KB
testcase_34 AC 56 ms
33,608 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

////////////
// ModInt //
////////////

// 四則演算の最も左に存在する値がModIntでなければキャストでバグる
// 例えばx = mint * 1000;やx = ModInt(1000) * mint;はいいがx = 1000 * mint;は駄目。
template<int64_t mod_ = 1'000'000'007>
class ModInt {
private:
	int64_t integer_;

public:
	constexpr ModInt(const int64_t initial_number = 0)
		: integer_(initial_number){}
	
	// 四則演算
	constexpr ModInt operator+(const ModInt& operand) const
	{
		ModInt ret{this->integer_ + operand.integer_};
		if (ret.integer_ >= mod_)
			ret.integer_ -= mod_;
		return ret;
	}
	constexpr ModInt operator-(const ModInt& operand) const
	{
		ModInt ret{this->integer_ - operand.integer_};
		if (ret.integer_ < 0)
			ret.integer_ += mod_;
		return ret;
	}
	constexpr ModInt operator*(const ModInt& operand) const
	{
		return {this->integer_ * operand.integer_ % mod_};
	}
	constexpr ModInt operator/(const ModInt& operand) const
	{
		return *this * (operand ^ (mod_ - 2));
	}

	// 単項演算子
	constexpr ModInt& operator++()
	{
		if (integer_ + 1 == mod_) integer_ = 0;
		else integer_++;
		return *this;
	}

	constexpr ModInt& operator--()
	{
		if (integer_ == 0) integer_ = mod_ - 1;
		else integer_--;
		return *this;
	}

	constexpr ModInt operator+()
	{
		return *this;
	}

	constexpr ModInt operator-()
	{
		if (integer_ == 0) return ModInt(0ll);
		else return ModInt(mod_ - integer_);
	}

	// 累乗
	constexpr ModInt operator^(const int64_t operand) const
	{
		ModInt ret{1}, pow_ope{this->integer_};
		for (int64_t pow{operand}; pow > 0; pow >>= 1)
		{
			if (pow & 1) ret *= pow_ope;
			pow_ope *= pow_ope;
		}
		return ret;
	}

	// 代入
	constexpr ModInt& operator=(const ModInt& operand)
	{
		this->integer_ = operand.integer_;
		return *this;
	}
	constexpr ModInt& operator+=(const ModInt& operand)
	{
		*this = *this + operand;
		return *this;
	}
	constexpr ModInt& operator-=(const ModInt& operand)
	{
		*this = *this - operand;
		return *this;
	}
	constexpr ModInt& operator*=(const ModInt& operand)
	{
		*this = *this * operand;
		return *this;
	}
	constexpr ModInt& operator/=(const ModInt& operand)
	{
		*this = *this / operand;
		return *this;
	}

	// その他
	constexpr operator int64_t() { return integer_; }

	constexpr ModInt getOne() const
	{
		return ModInt(1ll);
	}
	constexpr ModInt getZero() const
	{
		return ModInt(0ll);
	}
};
using Mint = ModInt<>;

////////////////
// 組み合わせ //
///////////////

template<int64_t mod_ = 1'000'000'007, int max_ = 200'000>
class Combination {
public:
	std::array<ModInt<mod_>, max_ + 1> inv, fact, finv;

	constexpr Combination()
	{
		inv[0] = inv[1] = fact[0] = fact[1] = finv[0] = finv[1] = 1;
		for (int num{2}; num <= max_; num++)
		{
			inv[num] = (mod_ - (int64_t)inv[mod_ % num] * (mod_ / num) % mod_) % mod_;
			fact[num] = num * fact[num - 1] % mod_;
			finv[num] = inv[num] * finv[num - 1] % mod_;
		}
	}

	constexpr ModInt<mod_> getCombi(const int n, const int r) const
	{
		if (r < 0 || n < 0 || n - r < 0) return 0;
		return fact[n] * finv[r] * finv[n - r];
	}

	constexpr ModInt<mod_> getPerm(const int n, const int r) const
	{
		if (r < 0 || n < 0 || n - r < 0) return 0;
		return fact[n] * finv[n - r];
	}
};
Combination<1'000'000'007, 1'000'000> combi;

int64_t calcGCD(int64_t a, int64_t b)
{
	while (a)
	{
		b %= a;
		std::swap(a, b);
	}
	return b;
}

int main()
{
	int64_t N, K;
	scanf("%lld%lld", &N, &K);
	std::vector<Mint> table(N + 1);
	for (int64_t i{N}; i > 1; i--)
	{
		if (N % i > 0 || K % i > 0) continue;
		table[i] = combi.getCombi(N / i, K / i);
		for (int64_t j{2 * i}; j <= N; j += i)
				table[i] -= table[j];
	}
	Mint sum;
	for (int i{2}; i <= N; i++)
		sum += table[i];
	std::cout << sum << std::endl;

	return 0;
}
0