題干：

鏈接：https://ac.nowcoder.com/acm/contest/317/D
來源：牛客網(wǎng)
?

小a和小b來到了一條布滿了黃金的街道上。它們想要帶幾塊黃金回去，然而這里的城管擔(dān)心他們拿走的太多，于是要求小a和小b通過做一個(gè)游戲來決定最后得到的黃金的數(shù)量。
游戲規(guī)則是這樣的：
假設(shè)道路長度為nn米(左端點(diǎn)為00，右端點(diǎn)為nn)，同時(shí)給出一個(gè)數(shù)kk(下面會(huì)提到kk的用法)
設(shè)小a初始時(shí)的黃金數(shù)量為AA，小b初始時(shí)的黃金數(shù)量為BB
小a從11出發(fā)走向n?1n?1，小b從n?1n?1出發(fā)走向11，兩人的速度均為1m/s1m/s
假設(shè)某一時(shí)刻(必須為整數(shù))小a的位置為xx，小b的位置為yy，若gcd(n,x)=1gcd(n,x)=1且gcd(n,y)=1gcd(n,y)=1，那么小a的黃金數(shù)量AA會(huì)變?yōu)锳?kx(kg)A?kx(kg)，小b的黃金數(shù)量BB會(huì)變?yōu)锽?ky(kg)B?ky(kg)
當(dāng)小a到達(dá)n?1n?1時(shí)游戲結(jié)束
小a想知道在游戲結(jié)束時(shí)A+BA+B的值
答案對109+7109+7取模

輸入描述:

一行四個(gè)整數(shù)n,k,A,Bn,k,A,B

輸出描述:

輸出一個(gè)整數(shù)表示答案

示例1

輸入

復(fù)制

4 2 1 1

輸出

復(fù)制

32

說明

初始時(shí)A=1,B=1A=1,B=1

第一個(gè)時(shí)刻如圖所示，小a在11，小b在33，滿足條件，此時(shí)A=1?21=2,B=1?23=8A=1?21=2,B=1?23=8

?

第二個(gè)時(shí)刻小a在22，小b在22，不滿足條件

?

第三個(gè)時(shí)刻小a在33，小b在11，滿足條件，此時(shí)A=2?23=16,B=8?21=16A=2?23=16,B=8?21=16

此時(shí)游戲結(jié)束A=2?23=16,B=8?21=16A=2?23=16,B=8?21=16

A+B=32A+B=32

示例2

輸入

復(fù)制

5 1 1 1

輸出

復(fù)制

2

備注:

保證3?n?108,1?A,B,k?10133?n?108,1?A,B,k?1013

解題報(bào)告：

? ?這題數(shù)據(jù)減弱成1e8了，，這樣就可以暴力了、、但是原先這題是1e13需要用歐拉函數(shù)相關(guān)知識(shí)。

? ?首先知道如果gcd(x,n) = 1? 則gcd(n-x,n) = 1.證明方法很多種，這里給出兩種，第一種：假設(shè)gcd(n-x,n) = d ( d != 1 ) ，則和第一個(gè)條件有矛盾；第二種：因?yàn)間cd(x,n) = 1 ，所以gcd(-x,n) = 1，所以gcd(n-x,n) = 1（即gcd(a,b)=1則gcd(a+b,b)=1）。而這題中我們找到了一個(gè)比較好的條件就是x+y=n，所以條件可以化簡成gcd(x,n) = 1 就行了。??

求出，可以推出（因?yàn)闅W拉函數(shù)都是兩兩配對的，除了2這個(gè)數(shù)，而2帶進(jìn)去也是可以整除的，所以等號(hào)右側(cè)一定可以除盡）最終答案就是

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9+7; ll qpow(ll a,ll k) {ll res = 1;while(k) {if(k&1) res = (res*a)%mod;a = (a*a)%mod;k>>=1;}return res; } ll E(ll n) {ll res = n;for(ll p = 2; p*p<=n; p++) {if(n%p==0) {res = res/p*(p-1);while(n%p==0) n/=p;}}if(n>1) res = res/n*(n-1);return res; } int main() {ll n,k,a,b; // cout<<E(4)<<endl;cin>>n>>k>>a>>b;cout << (a+b) * qpow(k,E(n)*n/2)%mod << endl;return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 317D】小a与黄金街道（数论，tricks）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。