UVALive 4225 Prime Bases 贪心
Prime Bases
题目连接:
Descriptionww.co
Given any integer base b >= 2, it is well known that every positive integer n can be uniquely represented in base b. That is, we can write
n = a0 + a1* b + a2* b* b + a3* b* b* b + ...
where the coefficients a0, a1, a2, a3, ... are between 0 and b-1 (inclusive).
What is less well known is that if p0, p1, p2, ... are the first primes (starting from 2, 3, 5, ...), every positive integer n can be represented uniquely in the "mixed" bases as:
n = a0 + a1* p0 + a2* p0* p1 + a3* p0* p1* p2 + ...
where each coefficient ai is between 0 and pi-1 (inclusive). Notice that, for example, a3 is between 0 and p3-1, even though p3 may not be needed explicitly to represent the integer n.
Given a positive integer n, you are asked to write n in the representation above. Do not use more primes than it is needed to represent n, and omit all terms in which the coefficient is 0.
Input
Each line of input consists of a single positive 32-bit signed integer. The end of input is indicated by a line containing the integer 0.
Output
For each integer, print the integer, followed by a space, an equal sign, and a space, followed by the mixed base representation of the integer in the format shown below. The terms should be separated by a space, a plus sign, and a space. The output for each integer should appear on its own line.
Sample Input
123
456
123456
0
Sample Output
123 = 1 + 12 + 4235
456 = 123 + 1235 + 22357
123456 = 123 + 6235 + 42357 + 1235711 + 4235711*13
Hint
题意
给你一个数,你需要拆成素数因子的形式
比如123 = 1 + 1*2+4*2*3*5
拆成n = a0 + a1* p0 + a2* p0* p1 + a3* p0* p1* p2 + ...
的形式
给你一个数,问你怎么拆
题解:
贪心去拆就好了让,素数乘积从大到小不断考虑
如果超过就减去就好了
然后不断贪
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 30;
bool flag[MAXN];
vector<int> P;
void GetPrime_1()
{
int i, j;
memset(flag, false, sizeof(flag));
for (i = 2; i < MAXN; i++)
if (!flag[i])
{
P.push_back(i);
for (j = i; j < MAXN; j += i)
flag[j] = true;
}
}
string get(int p)
{
string k;
while(p)
{
k+=(char)(p%10+'0');
p/=10;
}
reverse(k.begin(),k.end());
return k;
}
int main()
{
GetPrime_1();
long long n;
while(cin>>n)
{
if(n==0)break;
long long ans = 1;
for(int i=0;i<P.size();i++)
ans*=P[i];
long long pre = n;
stack<int> S;
for(int i=P.size()-1;i>=0;i--)
{
S.push(n/ans);
n=n%ans;
ans/=P[i];
}
printf("%lld =",pre);
int first = 1;
if(n)
{
printf(" 1");
first = 0;
}
for(int i=0;i<P.size();i++)
{
if(S.top()==0)
{
S.pop();
continue;
}
if(!first)
printf(" +");
first=0;
printf(" %d",S.top());
S.pop();
for(int j=0;j<=i;j++)
{
printf("*%d",P[j]);
}
}
printf("\n");
}
}
最新文章
- cut命令
- 谷歌大牛 Rob Pike 的 5 个编程原则
- 组件Newtonsoft.Json实现object2json转换
- ACM 数独
- sscanf函数和正则表达式
- Yii中设置时间分区
- 重温CSS之背景、文本样式
- RESTEasy 3.X Helloworld
- oracle 11g R2安装报错ORA-00604及ORA-06553的原因及解决方法
- 树莓派常用Linux命令
- EF添加
- 【Linux】Linux系统硬链接和软链接
- Machine Learning、Date Mining、IR&;NLP 会议期刊论文推荐
- pageadmin CMS网站制作教程:栏目单页内容如何修改
- Test checkout of feature &#39;Compiler&#39; failed 解决方法(转载)
- 给 C# Expression Evaluator 增加中文变量名支持
- [LeetCode] “全排列”问题系列(一) - 用交换元素法生成全排列及其应用,例题: Permutations I 和 II, N-Queens I 和 II,数独问题
- transient是干嘛的
- C# 64位win7下DllImport LoadLibrary函数失败 z
- 亲测SQLServer的最大连接数