如果发现广告等破坏行为，请尽量将条目恢复到较早的版本而不是把相应内容直接删除，谢谢合作。

URAL/1356

来自"NOCOW"

跳转到: 导航, 搜索

。。。

jiong~

本人猜想分解出来的不多于3个质数中

至多有1个大于sqrt(10^9)。。。

结果就写了个暴力dfs。。。

就AC了~无语啊！ 

#include <iostream>
#include <cmath>
using namespace std;
const int maxn=31623;
int T,n,tot=0,d,q[4],p[3402];
bool found,prime[maxn+1]={false};
inline bool IsPrime(int x)
{
    if (x <= maxn)  return !prime[x];
    int sqrt_x=(int)sqrt((double)x);
    for (int i=2;i<=sqrt_x;++i)
        if (x%i == 0)
            return false;
    return true;
}
inline void dfs(int k,int x,int y)
{
    if (found)  return;
    if (k == 1)
    {
        if (IsPrime(x))
        {
            for (int i=d;i>1;--i)
                cout << p[q[i]] << ' ';
            cout << x << endl;
            found=true;
        }
        return;
    }
    for (int i=y;i<=tot;++i)
    {
        if (p[i]*k > x)  return;
        q[k]=i;
        dfs(k-1,x-p[i],i);
    }
}
int main()
{
    cin >> T;
    for (int i=2;i<=maxn;++i)
        if (!prime[i])
        {
            int j=i*i;
            while (j <= maxn)
            {
                prime[j]=true;
                j+=i;
            }
            p[++tot]=i;
        }
    while (T--)
    {
        cin >> n;
        d=0,found=false;
        while (!found)
            dfs(++d,n,1);
    }
    return 0;
}
//by zzy
来自"http://www.nocow.cn/index.php/URAL/1356"
个人工具