SPOJ - LOCKER 数论贪心

题意:求出\(n\)拆分成若干个数使其连乘最大的值

本题是之江学院网络赛的原题,计算规模大一点,看到EMAXX推荐就做了

忘了大一那会是怎么用均值不等式推出结果的(还给老师系列)

结论倒还记得:贪心分解3,不够就用2凑

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<string>

#include<vector>

#include<stack>

#include<queue>

#include<set>

#include<map>

#define rep(i,j,k) for(register int i=j;i<=k;i++)

#define rrep(i,j,k) for(register int i=j;i>=k;i--)

#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])

#define iin(a) scanf("%d",&a)

#define lin(a) scanf("%lld",&a)

#define din(a) scanf("%lf",&a)

#define s0(a) scanf("%s",a)

#define s1(a) scanf("%s",a+1)

#define print(a) printf("%lld",(ll)a)

#define enter putchar('\n')

#define blank putchar(' ')

#define println(a) printf("%lld\n",(ll)a)

#define IOS ios::sync_with_stdio(0)

using namespace std;

const int maxn = 1e6+11;

const int oo = 0x3f3f3f3f;

const double eps = 1e-7;

typedef long long ll;

ll read(){

    ll x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

ll fpw(ll a,ll n,ll mod){

	ll ans=1;

	while(n){

		if(n&1) ans=(ans*a)%mod;

		n>>=1;

		a=(a*a)%mod;

	}

	return ans;

}

int main(){

	int T=read();

	const int mod = 1e9+7;

	while(T--){

		ll n=read();

		ll ans=0;

		if(n%3==0){

			ans=fpw(3,n/3,mod);

		}else if(n%3==1){

			if(n==1)ans=1;

			else ans=fpw(3,n/3-1,mod)*4;//3 1 -> 2 2

		}else{

			if(n==2)ans=2;

			else ans=fpw(3,n/3,mod)*2;//3 2

		}

		println((ans%mod));

	}

	return 0;

}

巴特西

SPOJ - LOCKER 数论贪心

最新文章

热门文章

巴特西

SPOJ - LOCKER 数论 贪心

最新文章

热门文章

SPOJ - LOCKER 数论贪心