简单解题思路

问题描述

给定一个无符号长整型数 a，将其表示为不同3的幂次方的和（每个幂次最多使用一次），并按特定格式输出这些幂次方。

核心思想

1. 预处理3的幂次：

   • 预先计算并存储 3^0 到 3^70 的值（使用字符串处理大数乘法）。

2. 二进制分解法：

   • 将 a-1 转换为二进制形式，每一位代表是否选用对应的3的幂次：
     • 二进制位为1 → 选用 3^位序；
     • 二进制位为0 → 不选用。

3. 格式化输出：

   • 按 { 幂次1, 幂次2, ... } 的格式输出选中的3的幂次。

关键步骤

1. 预处理阶段：

   • 使用字符串乘法计算 da[i] = 3^i（i 从0到70），避免数值溢出。

2. 输入处理：

   • 读取输入 a，若为0则终止程序；
   • 计算 a = a - 1（调整索引）。

3. 二进制分解与输出：

   • 遍历 a 的二进制位，若某位为1，则输出对应的 3^位序；
   • 按逗号分隔多项，最后用花括号包裹。

示例说明

• 输入：7
  二进制分解：7-1 = 6 → 110（二进制）
  输出：{ 3, 9 }（即 3^1 + 3^2）。

总结

• 核心算法：大数乘法（字符串处理） + 二进制分解。
• 适用场景：需要处理极大整数或特定数学表示的题目。
• 优化点：预计算幂次提升效率，二进制分解避免重复计算。

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
string mul(string a, string b)
{
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	int ta[200];
	int tb[200];
	int tc[200];
	memset(ta,0,sizeof(ta));
	memset(tb,0,sizeof(tb));
	memset(tc,0,sizeof(tc));
	for(int i=0;i<a.size();i++)
	{
		ta[i]=a[i]-'0';
	}
	for(int i=0;i<b.size();i++)
	{
		tb[i]=b[i]-'0';
	}
	for(int i=0;i<a.size();i++)
	{
		for(int j=0;j<b.size();j++)
		{
			tc[i+j]=tc[i+j]+ta[i]*tb[j];
		}
	}
	int jw=0;
	for(int i=0;i<199;i++)
	{
		int t=tc[i];
		tc[i]=(t+jw)%10;
		jw=(t+jw)/10;
	}
	int i;
	for(i=198;i>0;i--)
	{
		if(tc[i]!=0)
		{
			break;
		}
	}
	string jg;
	for(;i>=0;i--)
	{
		jg=jg+(char)(tc[i]+'0');
	}
	return jg;
}
int main()
{	
	string da[80];
	da[0]="1";
	for(int i=1;i<=70;i++)
	{
		da[i]=mul(da[i-1],"3");
		//cout<<da[i]<<endl;
	}
	unsigned long long a;//  unsigned __int64
 
	while(cin>>a)
	{
		if(a==0)
		{
			break;
		}
		a=a-1;		
		cout<<"{ ";
		int ws=0;
		while(a!=0)
		{
			if(a&1)
			{
				cout<<da[ws];
				if(a>>1)
				{
					cout<<", ";
				}
			}
			ws++;
			a=a>>1;
		}
		cout<<" }"<<endl;
	}	
	return 0;
}