题目意思

给你四个数字 n, k, a, b, 小a和 小b 分别从 1 走到 n-1, 从 n-1 走到 1, 每走一次长度为1
设x为 a 当前的位置 ， y为 b当前的位置
当gcd(x, n) == 1 && gcd(y, n) == 1 时候， a += kx ，b += y。
求a+b 答案模 1e9+7

题解

  1. 当x与n互质时候， （n-x）也与n互质，所以此题其实等价于 求n以内与n互质的数的和，即欧拉函数n*Φ(n)/2
  2. 由于指数太大用快速幂

通过代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll a, b, k;
int n;
 
ll ksm(ll a, ll b){//快速幂
    ll ans = 1;
    while(b){
        if(b&1){
            ans = ans * a % mod;
        }
        a = a*a % mod;
        b >>= 1;
    }
    return ans;
}
ll eular(ll x){//欧拉函数
    ll ans = x;
    for(ll i = 2; i*i <= x; ++i){
        if(x % i == 0){
            ans = ans / i * (i - 1);
            while(x % i == 0){
                x /= i;
            }
        }
    }
    if(x > 1){
        ans = ans / x*(x-1);
    }
    return ans;
}
int main(){
    cin>>n>>k>>a>>b;
    ll c = (a + b) % mod;
    ll ans = n*eular(n)/2;
    ans = c * ksm(k, ans) % mod;
    cout<<ans<<endl;
    return 0;
}