小a与黄金街道 拓展欧拉定理

前置知识：欧拉函数

φ函数的值 　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=223那么φ（12）=12（1-1/2）(1-1/3)=4)
----摘自百度

接下来怎么求欧拉函数呢

LL mul(LL x, LL y,LL p) {
    LL ans=0;
    while(y){
        if(y&1)ans+=x%p;
        y>>=1;
        x+=x%p;
    }
    return ans ;
}
LL Phi(LL N) {
    LL ans = 1;
    for(LL i = 2; i * i <= N; i++) {
        if(!(N % i)) {
            ans = mul(ans, i - 1); N /= i;
            while(!(N % i)) ans *= i, N /= i;
        }
    }
    if(N ^ 1) ans *= N - 1;//n是否为1
    return ans;
}

O(根号n)的复杂度，加上位运算
是我见过挺好的模板

小a与黄金街道
反正意思就不说了
挺巧妙的

1到n的所有gcd(n,x)==1的所有x数的和为n*φ(n)/2

牛客上的题解有说怎么来的

所以呢
这题套公式就好了
以下代码出自题解

#include<bits/stdc++.h>
#define LL long long
#define int long long  
using namespace std;
const LL mod = 1e9 + 6, mod2 = mod + 1;
LL N, K, A, B;
LL add(LL x, LL y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
LL mul(LL x, LL y) {
    return 1ll * x * y % mod;
}
LL fp(LL a, LL p, LL mod) {
    p %= mod;
    LL base = 1;
    while(p) {
        if(p & 1) base = base * a % mod;
        a = a * a % mod; p >>= 1;
    }
    return base;
}
LL Phi(LL N) {
    LL ans = 1;
    for(LL i = 2; i * i <= N; i++) {
        if(!(N % i)) {
            ans = mul(ans, i - 1); N /= i;
            while(!(N % i)) ans *= i, N /= i;
        }
    }
    if(N ^ 1) ans *= N - 1;
    return ans;
}
signed main() {
    cin >> N >> K >> A >> B;
    LL Lim = 1e13;
    assert(A >= 1 && A <= Lim && B >= 1 && B <= Lim);
    LL tmp = ((N % mod) * ((Phi(N) / 2) % mod) % mod) ;
    LL ans = (A + B) % mod2 * fp(K % mod2, tmp, mod2) % mod2;
    cout << ans;
    return 0;
}

这个signed main也很秀
long long 不能作为主函数类型，而防止int溢出，很秀的操作

assert终止函数

这是个拓展欧拉定理，吉比特杯学到的

因为Phi(1e9+7)=1e9+6
所以那个指数模的就是1e9+6

原来如此

今儿就到这