用小号做的div2
A：竟然看错了排序顺序。。。白白WA了两发
注意读入一整行（包括空格）：getline(cin,st) 【gets也是资瓷的
#include<iostream>
using namespace std;
string s[];
int d[];
int T,N; void qsort(int l,int r)
{
int i=l,j=r;
int m=(l+r)/;
int mid=d[m];
while(i<j)
{
while(d[i]<mid) i++;
while(d[j]>mid) j--;
if(i<=j)
{
int tmp=d[i];
d[i]=d[j];
d[j]=tmp;
string ts=s[i];
s[i]=s[j];
s[j]=ts;
i++;
j--;
}
}
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
} int main()
{
string st;
cin>>T;
while(T--)
{
cin>>N;
for(int i=;i<=N;i++)
{
getline(cin,st);
//cin>>s[i]>>d[i];
int tl=st.length();
int la=st[tl-]-'';
int lb=st[tl-]-'';
int lc=st[tl-]-'';
int ld=st[tl-]-'';
d[i]=ld*+lc*+lb*+la;
//cout<<i<<" "<<d[i]<<endl;
s[i]=st;
} qsort(,N);
for(int i=N;i>=;i--)
{
//cout<<s[i]<<endl;
int tl=s[i].length();
string tms=s[i];
for(int j=;j<=tl-;j++)
cout<<tms[j];
cout<<endl;
}
}
}
B：自己YY的方法
其实就是找乘积的最小非质数因子
先判断无解的情况：所有数都是1 or 只有一个非1的数且是质数，剩下的都是1
若有解：对每个a[i]都分解质因子，找出每个a[i]最小的和第二小的质因子
然后把所有的质因子们放一起排序，取最小的两个相乘既是解。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<ctime>
using namespace std;
#define LL long long
int T,N;
LL a[];
LL sm[]; //**********************************************
// pollard_rho算法进行质因素分解
//*********************************************
long long factor[];//质因素分解结果（刚返回时是无序的）
//注意factor里是每个质因数。比如N=8，那么factor[0..2]={2,2,2} (2^3=8)
int tol;//质因素的个数，编号0~tol-1 const int S = ; //随机算法判定次数，一般8~10就够了
//计算ret = (a*b)%c
long long mult_mod(long long a,long long b,long long c)
{
a %= c;
b %= c;
long long ret = ;
long long tmp = a;
while(b)
{
if(b & )
{
ret += tmp;
if(ret > c)ret -= c;//直接取模慢很多
}
tmp <<= ;
if(tmp > c)tmp -= c;
b >>= ;
}
return ret;
}
//计算 ret = (a^n)%mod
long long pow_mod(long long a,long long n,long long mod)
{
long long ret = ;
long long temp = a%mod;
while(n)
{
if(n & )ret = mult_mod(ret,temp,mod);
temp = mult_mod(temp,temp,mod);
n >>= ;
}
return ret;
}
//通过 a^(n-1)=1(mod n)来判断n是不是素数
// n-1 = x*2^t中间使用二次判断
//是合数返回true,不一定是合数返回false
bool check(long long a,long long n,long long x,long long t)
{
long long ret = pow_mod(a,x,n);
long long last = ret;
for(int i = ; i <= t; i++)
{
ret = mult_mod(ret,ret,n);
if(ret == && last != && last != n-)return true;//合数
last = ret;
}
if(ret != )return true;
else return false;
}
//**************************************************
bool Miller_Rabin(long long n)
//是素数返回true,(可能是伪素数)
//不是素数返回false
{
if(n==) return true;
if( n < )return false;
if( n == )return true;
if( (n&) == )return false;//偶数
long long x = n - ;
long long t = ;
while( (x&)== )
{
x >>= ;
t++;
}
rand();/* *************** */
for(int i = ; i < S; i++)
{
long long a = rand()%(n-) + ;
if( check(a,n,x,t) )
return false;
}
return true;
} long long gcd(long long a,long long b)
{
long long t;
while(b)
{
t = a;
a = b;
b = t%b;
}
if(a >= )return a;
else return -a;
}
//出一个因子
long long pollard_rho(long long x,long long c)
{
long long i = , k = ;
srand(time(NULL));
long long x0 = rand()%(x-) + ;
long long y = x0;
while()
{
i ++;
x0 = (mult_mod(x0,x0,x) + c)%x;
long long d = gcd(y - x0,x);
if( d != && d != x)return d;
if(y == x0)return x;
if(i == k)
{
y = x0;
k += k;
}
}
}
//对 n进行素因子分解，存入factor. k设置为107左右即可
void findfac(long long n,int k)
{
if(n == )return;
if(Miller_Rabin(n))
{
factor[tol++] = n;
return;
}
long long p = n;
int c = k;
while( p >= n)
p = pollard_rho(p,c--);//值变化，防止死循环k
findfac(p,k);
findfac(n/p,k);
} int main()
{
cin>>T;
while(T--)
{
cin>>N;
int acc=,occ=;
for(int i=;i<=N;i++)
{
cin>>a[i];
if(Miller_Rabin(a[i])) acc++;
if(a[i]==) occ++;
}
if(((occ==N-)&&(acc==))||(occ==N))
cout<<"-1"<<endl;
else
{
int tot=;
for(int i=;i<=N;i++)
{
tol = ;
memset(factor,,sizeof(factor));
findfac(a[i],);
//此时factor[0..tol-1]存放的就是所有质因数（无序）
sort(factor,factor+tol);
//cout<<a[i]<<" "<<tol<<endl;
//cout<<factor[0]<<factor[1]<<factor[2]<<endl;
if(factor[]!=)
{
tot++;
sm[tot]=factor[];
}
if(factor[]!=)
{
tot++;
sm[tot]=factor[];
}
}
sort(sm+,sm+tot+);
cout<<sm[]*sm[]<<endl;
} }
}