[题解]2018-02-08解题报告

oi
  1. 1. t1:
  2. 2. Qizy的指数
    1. 2.1. 题目描述
    2. 2.2. 输入描述
    3. 2.3. 输出描述
    4. 2.4. 样例1 输入
    5. 2.5. 样例1 输出
    6. 2.6. 样例2 输入输出
    7. 2.7. 数据范围及约定
    8. 2.8. 题解

110…还行..

t1:

Qizy的指数

题目描述

求$a^{n!}(mod \; p)$

输入描述

输入文件为$exp.in$
第一行,一个整数$T$,表述数据组数
接下来$T$行,每行三个正整数,表示$ai, ni, pi$

输出描述

输出文件为$exp.out$
$T$行,每行一个整数表示第$i$组数据的答案

样例1 输入

2
2 1 2
3 3 2

样例1 输出

0
1

样例2 输入输出

见选手目录下的$exp/exp2.in$与$exp/exp2.ans$
$Lovingly\;prepared\;by\;Qizy$

数据范围及约定

对于前30% 的数据:$1 \leq a_i,n_i,p_i \leq 10$
对于90% 的数据:$1 \leq a_i,n_i,p_i \leq 10^5$
对于100% 的数据:$1 \leq a_i,n_i,p_i \leq 10^7, T \leq 10$
得分:90

题解

#include <bits/stdc++.h>   
using namespace std;   
int t, a, n, p;   
// O(n\log{n})   
// a^{n!} <(-_-)>   
inline int pow(int a, int n, int p) {   
    // kuaisumi   
    long long ans = 1;   
    long long tempo = a;   
    int as = log(n) / log(2) + 2;   
    for (int i = 0; i < as; ++i) { // pow   
        if(n & (1 << i))   
            ans = (long long)(ans * tempo) % p;   
        tempo = (long long)(tempo * tempo) % p;   
    }   
    return ans % p;   
}   
int main() {   
    freopen("exp.in", "r", stdin);   
    freopen("exp.out", "w", stdout);   
    cin.tie(0);   
    ios::sync_with_stdio(false);   
    cin >> t;   
    while(t--) {   
        cin >> a >> n >> p;   
        long long ans = pow(a, n, p);   
        for (int i = 0; i < n; ++i) {   
            ans = pow(ans, n - i, p);   
        }   
        cout << ans % p << endl;   
    }   
}

其实是一个快速幂,100分正解需要费马小定理…
t2: …回家用typora反编译