Power Tower

NC229016. Power Tower

描述

牧师们想要建造一座塔来代表他们神的力量。塔通常由带电的岩石制成。它是在稀有魔法的帮助下通过悬浮塔的当前顶部并在其底部添加岩石而建造的。如果由 $\ k - 1$ 块岩石建造的顶部具有功率 $\ p$ ，并且我们想要添加带有功率 $\ w_k$ 的岩石，那么新塔的功率值将是 $\ \{w_k\}^p$ 。

岩石从最后一个添加到第一个。即对于序列 $\ w_1, ..., w_m$ 的幂值将是

塔建成后，其威力可能非常大。但是牧师仍然想获得一些关于它的信息，即他们想知道一个称为累积功率的数字，它是取模 $\ m$ 的功率的值。牧师有 $\ n$ 块石头，编号从 $\ 1$ 到 $\ n$ 。他们要求您计算如果他们用编号为 $\ l, l + 1, ..., r$ 的岩石建造这座塔，该塔将具有多少累积功率值。

输入描述

第一行包含两个整数 和。

第二行包含个整数，这是牧师拥有的岩石的力量。

第三行包含一个整数，这是牧师向您查询的数量。

接下来行的第行包含两个整数和。

输出描述

输出 个整数。它们中的第 个表示，如果用岩石 建造，塔将具有的累积功率量。

示例1

输入:

6 1000000000
1 2 2 3 3 3
8
1 1
1 6
2 2
2 3
2 4
4 4
4 5
4 6

输出:

说明:

$\ 3^{27} = 7625597484987$

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 878ms, 内存消耗: 1772K, 提交时间: 2023-08-10 16:53:13

#include<cstdio>
#include<algorithm>
typedef long long ll;
int h[35],a[100005];
int phi(int x){
	int y=x;
	for(int i=2;i*i<=x;++i)
		if(!(x%i)){
		y=y/i*(i-1);
		while(!(x%i)) x/=i;
	}
	if(x!=1) y=y/x*(x-1);
	return y;
}
int f(ll x,int y){return x<=y?x:(x%y+y);}
ll p2(ll x,int y,int p){ll z=1;for(;y;y>>=1,x=f((ll)x*x,p)) if(y&1) z=f((ll)z*x,p);return z;}
int r;
int solve(int x,int z){
	if(h[z]==1) return 1;
	if(x==r+1) return 1;
	return p2(a[x],f(solve(x+1,z+1),h[z+1]),h[z]);
}
int main(){
	int n,q,l;
	scanf("%d%d",&n,&h[0]);
	for(int i=1;;++i){
		h[i]=phi(h[i-1]);
		if(h[i]==1) break;
	}
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&l,&r);
		printf("%d\n",solve(l,0)%h[0]);
	}
	return 0;
}

上一题

下一题

详情