JOI 春合宿 2007 day2-2 Fermat (難易度 7)

これ FFT を使えば でもできるね。実際は で間に合う。

• ジャッジページ
• 問題文

問題概要

正の素数 と、正の整数 が与えられる。

• 
• は 以上 以下の整数

を満たすような の組の個数を求めよ。

制約

• 
• は素数
• 

考えたこと

まずは次のように集計処理をしよう。このように、「〜が何個あるか」という情報に変換して考えるのは典型！！

• num[v] ← となるような整数 () の個数

これは繰り返し二乗法で計算すれば でできる。

統合する

配列 num が求められたら、それを使って次の配列を求めよう。

• num2[v] ← となるような整数 の組の個数

これは単純には次のような処理で で求められる！

vector<long long> num2(P, 0);
for (int u = 0; u < P; ++u) {
    for (int v = 0; v < P; ++v) {
        num2[(u+v)%P] += num[u] + num[v];
    }
}

これを求めておけば、あとは答えは次のように求められる。

long long res = 0;
for (int v = 0; v < P; ++v) {
    res += num2[v] + num[v];
}

コード

計算量は となる。

なお、num2 を求める部分は、FFT を用いれば でできる。よってこの問題は でもできるので、, でも解ける。

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

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    long long P, N;
    cin >> P >> N;
    vector<long long> num(P, 0), num2(P, 0);
    for (int v = 0; v < P; ++v) num[modpow(v, N, P)]++;
    for (int u = 0; u < P; ++u) {
        for (int v = 0; v < P; ++v) {
            int s = (u + v >= P ? u + v - P : u + v);
            num2[s] += num[u] * num[v];
        }
    }
    long long res = 0;
    for (int v = 0; v < P; ++v) res += num2[v] * num[v];
    cout << res << endl;
}