欧拉定理

定理

讯享网
感觉这个定理降幂的时候用的多一点

题1

题面

思路

对于每一个数字ai，出现的次数为$A_i=C_{n-1}^{k-1}$

排序后，若ai为最大值，则作为最大值出现的次数为$B_i=C_i^{k-1}$

排序后，若ai为最小值，则作为最大值出现的次数为$C_i=C_{n-i-1}^{k-1}$

那么ai的贡献为${a_i}^{A-B-C}$,但是指数太大，需要降幂

因为1e9+7是质数，所以${a_i}^{A-B-C}(modp)$ = ${a_i}^{A-B-C(modphi(p))}(modp)$

故对于组合数可以直接$n^2$预处理

代码

#include <iostream> #include <cstdio> #include <set> #include <list> #include <vector> #include <stack> #include <queue> #include <map> #include <string> #include <sstream> #include <algorithm> #include <cstring> #include <cstdlib> #include <cctype> #include <cmath> #include <fstream> #include <iomanip> //#include <unordered_map> using namespace std; #define dbg(x) cerr << #x " = " << x << endl; typedef pair<int, int> P; typedef long long ll; #define FIN freopen("in.txt", "r", stdin);freopen("out.txt","w",stdout); const int MAXN = 1e3+5; const int mod = 1e9+7; ll a[MAXN]; ll C[MAXN][MAXN]; void init() { 
    for(int i = 0; i < MAXN; i++) { 
    C[i][0] = 1; for(int j = 1; j <= i; j++) { 
    C[i][j] = (C[i-1][j] + C[i-1][j-1]) % (mod - 1); } } } ll qpow(ll a, ll b) { 
    ll ans = 1, base =a ; while(b) { 
    if(b & 1) { 
    ans = ans * base % mod; } base = base * base % mod; b >>= 1; } return ans; } int main() { 
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(); int t; cin >> t; while(t--) { 
    int n, k; cin >> n >> k; for(int i = 0; i < n; i++) { 
    cin >> a[i]; } sort(a, a + n); ll ans = 1; for(int i = 0; i < n; i++) { 
    ll mi = C[n-1][k-1] - C[i][k-1] - C[n-i-1][k-1]; mi = (mi % (mod - 1) + (mod - 1)) % (mod - 1); ll tmp = qpow(a[i], mi); ans = (ans * tmp) % mod; } cout <<ans << endl; } return 0; } 

题2

题面

思路

代码

讯享网#include <iostream> #include <cstdio> #include <set> #include <list> #include <vector> #include <stack> #include <queue> #include <map> #include <string> #include <sstream> #include <algorithm> #include <cstring> #include <cstdlib> #include <cctype> #include <cmath> #include <fstream> #include <iomanip> //#include <unordered_map> using namespace std; #define dbg(x) cerr << #x " = " << x << endl; typedef pair<int, int> P; typedef long long ll; #define FIN freopen("in.txt", "r", stdin);freopen("out.txt","w",stdout); string a, b; ll getnum(string s, int mod) { 
    ll ret = 0; for(int i = 0; i < s.size(); i++) { 
    ret = ret * 10 + (s[i] - '0') % mod; ret %= mod; } return ret % mod; } int mypow(string s, int n, int mod) { 
   ///s^n%mod int a = getnum(s, mod), ret = 1; while(n--) ret = ret * a % mod; return ret; } int phi(int x) { 
    if(x == 10) return 4; if(x == 4) return 2; if(x == 2) return 1; return -1; } ll solve(string s, int n, int mod) { 
    int a = getnum(s, mod); if(mod == 1) return 1; if(n == 1) return a %mod + mod; int mi = solve(s, n-1, phi(mod)); return mypow(s, mi, mod) + mod; } int main() { 
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> a >> b; if(a == "1" || b == "1") { 
    cout << a[a.length() - 1] << endl; } else { 
    int n = 0; if(b.size() > 2) { 
    n = 100; } else n = getnum(b, 100); int p = solve(a, n-1, phi(10)); cout << mypow(a, p, 10) << endl; } return 0; }