Algoogle

Algorithm for Programming Contest

JOI 春合宿 2007 Fermat

Category: JOI Tag: dp

Fermat

問題概要


nとpが与えられたとき以下の式を満たす(x,y,z)の組はいくつあるか()

解法


0からp-1までのn乗(mod p)を列挙して各値の個数を数える.
あとはxとyの組を列挙してその和(mod p)との組合せを求める.

コード


(Fermat.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

int p, n, powc[10010];

int pow_mod(int x, int k, int p)
{
        if(!k) return 1;
        if(k%2) return x*pow_mod(x,k-1,p)%p;
        else return pow_mod(x*x%p,k/2,p);
}

int solve()
{
        for (int i = 0; i < p; i++)
                powc[pow_mod(i,n,p)]++;
        int ans = 0;
        for (int i = 0; i < p; i++){
                ans += powc[i]*powc[i]*powc[(i+i)%p];
                for (int j = i+1; j < p; j++)
                        ans += 2*powc[i]*powc[j]*powc[(i+j)%p];
        }
        return ans;
}

void input()
{
        cin >> p >> n;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments