AtCoder Regular Contest 051 C - 掛け算

問題

C: 掛け算 - AtCoder Regular Contest 051 | AtCoder

解法

まず数列の最大値を超えないギリギリまで愚直にシミュレートする。
ここは(楽をして)priority_queueを使った。
このシミュレートは、数列の最大値をXとすると、 しかかからない。

ここまでやると、どの要素をA倍しても最大値になる状態になる。
これは数列全体を何倍しても保たれる性質なので、A倍しなきゃいけない残りの回数がN以下になるまで、繰り返し二乗法を使って一気に進める。
残った端数分の回数は、素直に小さい要素から順にかける。

繰り返し二乗法部分はなので、全体で。

A=1のケースに注意する。

実装

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MOD = 1000000007;

int N, A, B, C[50];

int Pow(int x, int n)
{
	if (n == 0) return 1;
	return Pow(x*x % MOD, n/2)*((n&1) ? x : 1) % MOD;
}

void Solve()
{
	if (A == 1)
	{
		sort(C, C + N);
		return;
	}
	priority_queue< int, vector<int>, greater<int> > pq;
	int ma = 0;
	for (int i = 0; i < N; i++)
	{
		ma = max(ma, C[i]);
		pq.push(C[i]);
	}
	while (B > 0 && pq.top()*A <= ma)
	{
		int t = pq.top(); pq.pop();
		pq.push(t*A);
		B--;
	}
	for (int i = 0; i < N; i++)
	{
		int k = B/N;
		if (i < (B % N)) k++;
		C[(N - B % N + i) % N] = pq.top()*Pow(A, k) % MOD;
		pq.pop();
	}
}

signed main()
{
	cin >> N >> A >> B;
	for (int i = 0; i < N; i++)
	{
		cin >> C[i];
	}
	Solve();
	for (int i = 0; i < N; i++)
	{
		printf("%lld\n", C[i]);
	}
	return 0;
}