Есть некоторые ограничения: 1≤T≤100 сумма N во всех тестовых случаях не превышает 10 ^ 7 1≤C≤10 ^ 9
#include<bits/stdc++.h>
using namespace std;
bool comp_func(int x,int y)
{
return x>=y;
}
vector<int> primeFac(int n)
{
vector<int> result;
while (n%2 == 0)
{
result.push_back(2);
n = n/2;
}
// n must be odd at this point. So we can skip
// one element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i = i+2)
{
// While i divides n, print i and divide n
while (n%i == 0)
{
result.push_back(i);
n = n/i;
}
}
// This condition is to handle the case when n
// is a prime number greater than 2
if (n > 2)
result.push_back(n);
return result;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;cin>>t;
while(t--)
{
int n,c;cin>>n>>c;
vector<int> d;
for(int i=0;i<n;i++)
d.push_back(i);
if(c==1)
{
for(int i=0;i<n;i++)
cout<<d[i]+1<<" ";
}
else{
vector<int> prime_fac=primeFac(c);
sort(prime_fac.begin(),prime_fac.end());
if(prime_fac.size()<n)
{
int c_2=count(prime_fac.begin(),prime_fac.end(),2);
int c_3=count(prime_fac.begin(),prime_fac.end(),3);
if(c_2!=0)
{
for(int i=0;i<c_3;i++)
{
d[i]+=3;
}
int pos=0;
for(pos=c_3;pos<n-(prime_fac.size()-c_3-c_2);pos++)
{
if(pos<c_3+c_2)
d[pos]+=2;
else
d[pos]+=1;
}
for(int i=c_2+c_3;i<prime_fac.size();i++)
{
d[pos++]+=prime_fac[i];
}
}
else
{
sort(prime_fac.begin(),prime_fac.end(),comp_func);
for(int i=n-1,j=0;i>=0 || j<prime_fac.size();i--,j++)
{
if(j<prime_fac.size())
d[i]+=prime_fac[j];
else
d[i]+=1;
}
}
for(int i=0;i<n;i++)
cout<<d[i]<<" ";
}
else
{
while(prime_fac.size()!=n)
{
prime_fac[0]*=prime_fac[1];
prime_fac.erase(prime_fac.begin()+1);
sort(prime_fac.begin(),prime_fac.end());
}
sort(prime_fac.begin(),prime_fac.end());
vector<int> diff;
for(int i=0;i<n-1;i++)
{
if(prime_fac[i+1]-prime_fac[i]<=1)
diff.push_back(prime_fac[i]);
else
{
diff.push_back(prime_fac[i]);break;
}
}
int size_dif=diff.size();
if(prime_fac[n-1]-diff[size_dif-1]<=1)
diff.push_back(prime_fac[n-1]);
sort(diff.begin(),diff.end(),comp_func);
if(diff.size()!=1)
{ int pos_t=0;
for(int i=0;i<diff.size();i++)
{
d[i]=diff[i]+i;
pos_t++;
}
for(int i=pos_t;i<n;i++)
{
d[i]=prime_fac[i]+i;
}
for(int i=0;i<n;i++)
cout<<d[i]<<" ";
}
else
{
for(int i=0;i<n;i++)
cout<<prime_fac[i]+i<<" ";
}
}
}
cout<<"\n";
}
return 0;
}
Самое большое, что я вижу здесь, этоС этим тоже может справиться int, так что я не думаю, что это ошибка типа данных.Единственная часть, скептически относящаяся к петлям, но я убедился, что они защищены от утечек с помощью условных выражений.Если кто-то может предложить какие-то изменения, пожалуйста, сделайте :), я мог бы сделать глупую ошибку.