欧拉定理（降幂）

欧拉定理

定理

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

题1

题面

思路

对于每一个数字ai，出现的次数为 A i = C n − 1 k − 1 A_i = C_{n-1}^{k-1} Ai​=Cn−1k−1​

排序后，若ai为最大值，则作为最大值出现的次数为 B i = C i k − 1 B_i = C_{i}^{k-1} Bi​=Cik−1​

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

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

因为1e9+7是质数，所以 a i A − B − C ( m o d p ) {a_i}^{A-B-C}(modp) ai​A−B−C(modp) = a i A − B − C ( m o d p h i ( p ) ) ( m o d p ) {a_i}^{A-B-C (mod phi(p))}(modp) ai​A−B−C(modphi(p))(modp)

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

代码

#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

题面

思路

一层一层套用欧拉降幂即可
因为只需要mod10，所以只需要记录10以内的欧拉函数，当只剩1的时候特判处理即可

代码

#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;
}