2007年 日本情報オリンピック春合宿OJ

Submission #1112534

Source codeソースコード

#include <iostream>

int pow_mod(int x, int n, int mod) {
    int ans = 1;
    
    while(n != 0) {
        if(n & 1)
            ans = (ans * x) % mod;
        
        x = (x*x) % mod;
        n >>= 1;
    }
    
    return ans;
}

int count[10010];

int main() {
    int p, n;
    
    std::cin >> p >> n;
    
    for(int i = 0; i < p; ++i) {
        ++count[pow_mod(i, n, p)];
    }
    
    int zero = 0;
    int cnt = 0;
    for(int i = 0; i < p; ++i) {
        zero += count[0] * count[i] * count[(p - i) % p];
        
        if(i > 0 && count[i] > 0)
            ++cnt;
    }
    
    int one = 0;
    for(int i = 0; i < p; ++i) { // x
        one += count[1] * count[i] * count[(p + 1 - i) % p];
    }
    
    std::cout << zero + one * cnt << std::endl;
}

Submission

Task問題 fermat - フェルマー方程式 (Fermat)
User nameユーザ名 Tsuzu
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 810 Byte
File nameファイル名
Exec time実行時間 2 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Set01 20 / 20 01
Set02 20 / 20 02
Set03 20 / 20 03
Set04 20 / 20 04
Set05 20 / 20 05

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01 AC 1 ms 256 KB
02 AC 1 ms 256 KB
03 AC 1 ms 256 KB
04 AC 2 ms 256 KB
05 AC 2 ms 256 KB