NKOJ 3743 奶牛求幂 （启发式搜索）

发表于 |
字数统计: 527字 | 阅读时长 ≈ 2min

P3743奶牛求幂

问题描述

约翰的奶牛想要快速计算出整数的P(1<=P<=20000)次幂。计算过程中它们只能使用两个存储器，每个存储器可以记录某个结果的值。
它们的第一个工作是初始化存储器的值：一个存底数x,另一个初值为1。
奶牛可以相乘或相除两个存储器中的值，并把结果存在其中某个存储器内，但存储器存的数字必须是整数。比如两个存储器存的数字分别是A和B，你可以做这些运算 AB，AA，B*B，A/B，B/A，A/A，B/B
例如，如果它们想要计算x^31,一种计算方法是：
这里写图片描述

因此，x^31可以通过6次计算得出。给出要计算的幂次，请你帮奶牛求出最少需要几次计算

输入格式

一个整数P

输出格式

一个整数，表示最少计算次数

样例输入 1

31

样例输出 1

6

样例输入 2

1023

样例输出 2

11

其他都好说，用log2来估价，最重要的是要用gcd剪枝，如果当前搜索到(u,v)这个数对，那么如果n不能被gcd(u,v)整除，那么显然可以return了。证明是显然的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
int n,k;
int gcd(int a,int b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
bool DFS(int x,int u,int v)
{
	if(x>k)return 0;
	if(u>v)u^=v^=u^=v;
	if((v<<(k-x))<n)return 0;
	if(n%gcd(u,v))return 0;
	if(u==v)return 0;
	if(v==n)return 1;
	int a=u+v,b=v-u,c=u+u,d=v+v;
	if(DFS(x+1,a,v))return 1;
	if(DFS(x+1,d,v))return 1;
	if(DFS(x+1,c,v))return 1;
	if(DFS(x+1,b,v))return 1;
	if(DFS(x+1,u,a))return 1;
	if(DFS(x+1,u,b))return 1;
	if(DFS(x+1,u,c))return 1;
	if(DFS(x+1,u,d))return 1;
	return 0;
}
int main()
{
	scanf("%d",&n);
	while(!DFS(0,0,1))k++;
	printf("%d",k);
}