| input | output |
|---|---|
3 1 2 3 |
1 |
4 2 2 2 2 |
infinity |
这题没加根号的优化会T， 别问我是怎么知道的 
题意：就是一列数字， 像他给的样例一样操作
{2, 3, 3, 6} turns it into array {gcd(2, 3), gcd(2, 3), gcd(2, 6), gcd(3, 3), gcd(3, 6), gcd(3, 6)}, that is {1, 1, 2, 3, 3, 3}.
然后问，不断这要操作，几遍可以得到都是1的数组。
做法： 暴力打个表发现 要么 只用1次 要么两次 要么 就是无穷的。
因为n很大，操作一次就要超时的。所以要在原始数组中想方法判断。
开始，我是通过暴力打表发现的，如果任何两个数都互质，那么只用一次就可以变成1。只要有两个数不互质，那么 就要2次才能都变1。 如果有三个数或以上 两两不互质 那么就要无穷次，不断循环下去了。
yy一下，发现这结论也是对的。 两个数不互质，一轮之后就变成只有非1 的数，再一轮 就全是1了。 如果有三个数以上两两不互质，那么他必然会再产生三个以上两两不互质的数，就无限循环下去，不会有都是1的情况出现了。
知道了结论，要想做法了。
找有没有三个数两两不互质，得for三层，是 肯定要超时的。 然后问了同学。。 只要因数分解就可以了。 分解的时候要注意， 比如8 可以分解为2*2*2， 但是8是一个数，所以算2这个素数个数的时候是只加1的。 然后判断最大的素数个数是多少。大于等于3，是无限，等于2是两次，等于1是一次，等于0 说明全是1，就是0次；
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#include <map>
#define INF 999999999
#define eps 0.00001
#define LL __int64d
#define pi acos(-1.0)
#define ll int //只能int 不然数组存不下
#define N 10000020
//prime[0,primenum)
ll prime[1000000], primenum;
bool Isprime[N+10];
//<=Max_Prime的素数
void PRIME(ll Max_Prime){
primenum = 0;
Isprime[0] = Isprime[1] = 0;
Isprime[2] = 1;
prime[primenum++] = 2;
for(ll i = 3; i <= Max_Prime; i++)
Isprime[i] = i&1;
for (ll i = 3; i <= Max_Prime; i+=2){
if(Isprime[i])
prime[primenum++] = i;
for (ll j = 0; j < primenum; j++){
if(prime[j] * i > Max_Prime)break;
Isprime[prime[j]*i] = 0;
if(i%prime[j] == 0)break;
}
}
}
int gcd(int n,int m){//最大公因数
if(n<m)
swap(n,m);
int tmp;
while(m){tmp=n;n=m;m=tmp%m;}
return n;
}
int lcm(int n,int m){//最小公倍数
return n*(m/gcd(n,m));//预防 m*n 超过整形，先除一下。
}
int flag;
int has[10000010];
void add(int x)
{
int tem=sqrt(1.0*x);
for(int i=0;i<primenum&&prime[i]<=tem&&x!=1;i++)
{
if(x%prime[i]==0)
{
x/=prime[i];
has[prime[i]]++;
}
while(x%prime[i]==0)
x/=prime[i];
}
if(x!=1)
has[x]++;
}
void cal()
{
for(int i=0;i<primenum;i++)
{
if(has[prime[i]]==2&&flag<2)
flag=2;
else if(has[prime[i]]>=3)
flag=3;
}
}
int a[10010];
int main()
{
PRIME(10000002);
int n;
while(scanf("%d",&n)!=EOF)
{
memset(has,0,sizeof has);
flag=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
add(a[i]);
if(a[i]!=1)
flag=1;
}
cal();
if(flag==3)
puts("infinity");
else
printf("%d\n",flag);
}
return 0;
}
ural 2003. Simple Magic 数论 因数分解
原文：http://blog.csdn.net/u013532224/article/details/43762227