救命欧拉筛+唯一分解TLE了
查看原帖
救命欧拉筛+唯一分解TLE了
1069246
cgdgt楼主2023/12/3 17:19
#include<bits/stdc++.h>
typedef long long ll;
using namespace std; 
ll prime[10000005]; 
ll a[1000005]; 
bool vis[10000005]; 
ll cnt=0; 
void primejudge(ll n) 
{ 
    memset(vis,false,sizeof(vis));
    vis[1]=true; 
    int i,j; 
    for(i=2;i<=n;i++) 
    { 
        if(!vis[i])
        {
            prime[cnt++]=i; 
        } 
        for(j=0;j<cnt&&i*prime[j]<=n;j++) 
        { 
            vis[i*prime[j]]=true; 
            if(i%prime[j]==0)
            {
                break;
            }
        } 
    } 
}
ll num(ll n)
{
    ll ans=1,x=1,y=1,z=1;
    for(ll i=0;i<n;i++)
    {
        if(a[i]!=1)
        {
            if(a[i]==a[i+1])
            {
                y++;
            }
            else
            {
                for(ll j=1;j<=y;j++)
                {
                    z*=a[i];
                    x+=z;
                }
                ans*=x;
                x=1;
            	y=1;
            	z=1;
            }
        }
    }
    return ans;
}
int main()
{ 
    primejudge(10000005);
    ll n,m=2,m2=2,ans; 
    ll i,index=0; 
    scanf("%lld",&n);
    while(m2<=n)
    {
        memset(vis,0,sizeof(vis));
        memset(a,0,sizeof(a));
        index=0;
        for(i=0;i<cnt&&prime[i]*prime[i]<=m;i++)
        { 
            while(m%prime[i]==0)
            {
                a[index++]=prime[i];
                m/=prime[i]; 
            }
            if(n==1) 
            {
                break; 
            }
        }
        if(n!=1)
        { 
            a[index++]=m;
        }
        ans=num(index);
        if(n==ans)
        {
            cout<<m2<<" ";
        }
        m=m2+1;
        m2++;
    }
    return 0;
}
2023/12/3 17:19
加载中...