小a与黄金街道（欧拉函数+快速幂）

链接：https://ac.nowcoder.com/acm/contest/317/D

来源：牛客网

题目描述

小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。

游戏规则是这样的：

假设道路长度为nn米(左端点为00，右端点为nn)，同时给出一个数kk(下面会提到kk的用法)

设小a初始时的黄金数量为AA，小b初始时的黄金数量为BB

小a从11出发走向n−1n−1，小b从n−1n−1出发走向11，两人的速度均为1m/s1m/s

假设某一时刻(必须为整数)小a的位置为xx，小b的位置为yy，若gcd(n,x)=1gcd(n,x)=1且gcd(n,y)=1gcd(n,y)=1，那么小a的黄金数量AA会变为A∗kx(kg)A∗kx(kg)，小b的黄金数量BB会变为B∗ky(kg)B∗ky(kg)

当小a到达n−1n−1时游戏结束

小a想知道在游戏结束时A+BA+B的值

答案对109+7109+7取模

输入描述:

一行四个整数n,k,A,Bn,k,A,B

输出描述:

输出一个整数表示答案

示例1

输入

复制

4 2 1 1

输出

复制

说明

初始时A=1,B=1A=1,B=1

第一个时刻如图所示，小a在11，小b在33，满足条件，此时A=1∗21=2,B=1∗23=8A=1∗21=2,B=1∗23=8

第二个时刻小a在22，小b在22，不满足条件

第三个时刻小a在33，小b在11，满足条件，此时A=2∗23=16,B=8∗21=16A=2∗23=16,B=8∗21=16

此时游戏结束A=2∗23=16,B=8∗21=16A=2∗23=16,B=8∗21=16

A+B=32A+B=32

示例2

输入

复制

5 1 1 1

输出

复制

备注:

保证3⩽n⩽108,1⩽A,B,k⩽10^13 3⩽n⩽10^8,1⩽A,B,k⩽10^13

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define mod 1000000007

ll eular(ll n){

    ll ret=1,i;

    for (i=2;i*i<=n;i++)

        if (n%i==0){

            n/=i,ret*=i-1;

            while (n%i==0)

                n/=i,ret*=i;

        }

    if (n>1)

        ret*=n-1;

    return ret;

}

ll power(ll a,ll b){

    ll res=1;

    while(b){

        if(b&1){

            b--;

            res=res*a%mod;

        }

        b/=2;

        a=a*a%mod;

    }

    return res%mod;

}

int main()

{

    //cout<<eular(4);

    ll n,k,a,b;

    cin>>n>>k>>a>>b;

    ll t=eular(n)*n/2%mod;

    cout<<(a+b)*power(k,t)%mod;

    return 0;

}

巴特西

小a与黄金街道（欧拉函数+快速幂）

题目描述

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

最新文章

热门文章