拆拆拆~
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.uestc.edu.cn/#/problem/show/1246
Description
给你一个数x，你有两个操作
1.分解质因数，如果x是一个合数，那么就将x分解质因数，然后进入操作2，否则输出这个数
2.将分解质因数中的乘号变成加号，执行操作1
问你最后输入多少？
Input
多组数据，大概10000组，每组数据仅包含一个正整数n(1<=n<=10^9)
Output
对于每组数据，输出一个整数，表示最后的数字。如果无法得到最后的数字，输出-1
Sample Input
1
2
4
6
8
10
Sample Output
1
2
-1
5
5
7
HINT
题意
题解：
暴力分解质因数，然后模拟就好了
复杂度sqrt(n)*logn（大概是这个
代码：
#include<iostream>
#include<stdio.h>
using namespace std; int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int now = n;
int sum = ;
int flag = ;
int pre = ;
while()
{
pre = now;
sum = ;
flag = ;
for(int i=;i*i<=now;i++)
{
if(now%i==)
flag = ;
}
if(flag == )
{
flag = now;
break;
}
for(int i=;i*i<=now;i++)
{
while(now%i==)
{
flag = ;
now/=i;
sum+=i;
}
if(now==)
break;
}
if(now>)
{
sum+=now;
now = ;
}
if(pre==sum)
{
flag = -;
break;
}
now = sum;
}
printf("%d\n",flag);
}
}