[C++] 純文本查看 復制代碼
#include<iostream>
#include<cstring>
#define endl '\n'
using namespace std;
char dp1[25][11000],dp2[25][251000];
bool prime[1000001];
bool can1ans(int i,int sum);
bool can2ans(int i,int prod);
bool can1ans(int i,int sum)
{
if(dp1[sum]!=-1)
return dp1[sum];
if(i==1)
return dp1[sum]= sum==2 || sum==3;
int cantAnsC=0;
for(int a=1;a<sum;a++)
{
int b=sum-a;
if(b<a)break;
if(!can2ans(i-1,a*b))
cantAnsC++;
if(cantAnsC>1)
return dp1[sum]=0;
}
if(cantAnsC==1)
return dp1[sum]=1;
throw;
}
bool can2ans(int i,int prod)
{
if(dp2[prod]!=-1)
return dp2[prod];
if(i==1)
return dp2[prod]= prime[prod];
int cantAnsC=0;
for(int a=1;a<prod;a++)
{
int b=prod/a;
if(b<a)break;
if(a*b!=prod)continue;
if(!can1ans(i-1,a+b))
cantAnsC++;
if(cantAnsC>1)
return dp2[prod]=0;
}
if(cantAnsC==1)
return dp2[prod]=1;
throw;
}
void setprime()
{
for(int i=0;i<=1000000;i++)
prime=1;
for(int i=2;i<=1000;i++)
if(prime)
for(int j=i+i;j<=1000000;j+=i)
prime[j]=0;
}
int main()
{
ios::sync_with_stdio(false);
//cin.tie(0);
setprime();
int T;
cin>>T;
while(T--)
{
memset(dp1,-1,sizeof dp1);
memset(dp2,-1,sizeof dp2);
int a,b;
cin>>a>>b;
for(int i=1;;i++)
{
if(i>5)
{
cout<<"-1 -1"<<endl;
break;
}
bool c1a=can1ans(i,a+b),c2a=can2ans(i,a*b);
if(c1a&&c2a)
cout<<i<<" "<<i<<endl;
else if(c1a)
cout<<i<<" "<<i+1<<endl;
else if(c2a)
cout<<i+1<<" "<<i<<endl;
else continue;
break;
}
}
}
[C++] 純文本查看 復制代碼
#include<iostream>
#include<cctype>
#include<algorithm>
using namespace std;
int apb(int n)
{
if(n<=3)return 1;
if(n==4)return 2;
if(n==5)return 4;
return 9999;
}
bool isprime(int n)
{
if(n<=1)return false;
for(int i=2;i<n;++i)
if(n%i==0)
return false;
return true;
}
int amb(int n)
{
if( n==1 || isprime(n) )
return 1;
if(n==4)return 3;
if(n==6)return 5;
return 9999;
}
int main()
{
int T,a,b;
cin>>T;
while(T--)
{
cin>>a>>b;
int N=apb(a+b);
int M=amb(a*b);
int m=min(N,M);
if( min(N,M) == 9999 )
cout<<"-1 -1\n";
else
{
if(N!=1) N=min(N,m+1);
if(M!=1) M=min(M,m+1);
cout<<N<<" "<<M<<'\n';
}
}
}