反素数研究

2019-01-15 本文已影响0人 strategist_614

反素数研究

定义：对于任何正整数 $n$ ,其约数个数记为 $f(n)$ ,例如 $f(6) = 4$ ,如果某个正整数 $n$ 满足：对任意正整数 $i(0<i<n)$ ，都有 $f(i)<f(n)$ ,那么称 $n$ 为反素数。
性质：
1.一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为 $x$ 的这个数 $n$ 尽量小。
2.同样的道理，如果 $n = 2^{t_1}*3^{t_2}*5^{t_3}*...$ 那么一定有 $t_1>=t_2>=t_3>=t_4...$ ,n的约数个数为 $(t_1+1)*(t_2+1)*(t_3+1)*...$
证明见~~算法竞赛进阶指南~~
模板(扒的)(加优化的)

void dfs(ll num,int k,int sum,int limit)
{//num: 当前枚举到的数 k:枚举到的第k大的质因子 sum:该数的约数个数 limit：质因子个数上限(重要剪枝)
    if(sum>maxsum)       //约数个数更多
    {
        maxsum=sum;
        ans=num;
    }
    if(sum==maxsum&&ans>num)  //约数个数相同，把最优解更新为较小值
    {
        ans=num;
    }
    if(k>16)                     //这里k>x; x至少满足prime[1]*prime[2]*prime[3]*...*prime[x]>x ,当x=16时，数据已超过10^18
        return;                  //当x=10时，数据已超过10^9
    ll temp=num;
    for(int i=1;i<=limit;i++)  //枚举每个质因子的个数
    {
        if(n/prime[k]<temp)    //n为上限,用除法防止溢出
            return;
        temp*=prime[k];
        dfs(temp,k+1,sum*(i+1),i);  //把limit置为i的原因见性质第二条
    }
}

模板~~自己的~~

void dfs(ll now,ll sum,ll k)
{//now 当前枚举到的数,sum 当前的约数个数,k枚举到第k个质数
   if(sum > maxsum)//当约数个数更多的时候更新
   {
      maxsum = sum;
      ans = now;
   }
   if(sum == maxsum && ans > now)//当约数个数相同时,取数最小的
   {
     ans = now;
   }
   if(k > 10) return ;//超过枚举的深度 return
   ll tmp = now;
   for(int i = 1;i <= 31;i++)
    {
        if(n / prime[k] < tmp) return ;//当前数值大于n时
        dfs(tmp*=prime[k],sum*(i+1),k+1);
    }
}

更优化的 ~~见杭电那道题~~
例题 1：
- 题目
  codeforces 27E
- 题意
  给一个数 $n$ ，求最小正整数 $x$ ,使得 $x$ 的约数个数为 $n$ .
- 分析

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
const ull INF = ~0ULL;
ull ans = INF;
int n;
void dfs(int dep,ull tmp,int num)
{
    if(num > n) return ;
    if(num == n && ans > tmp) {ans = tmp;}
    for(int i = 1;i<=63;i++)
    {
        if(ans / prime[dep] < tmp) break;
        dfs(dep+1,tmp *= prime[dep],num*(i+1));
    }
}
int main ()
{
    cin>>n;
    dfs(0,1,1);
    cout<<ans<<endl;
    return 0 ;
}

例题 2：
- 题目
  反素数 P1463
- 题意
  给定一个 $n$ ,求出不超过 $n$ 的反素数
- 分析
  反素数经典题：
  就是采用DFS去搜索满足反素数的性质的答案。具体解释见代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e9;
const int prime[] = {0,2,3,5,7,11,13,17,19,23,29};
void solve()
{
    int maxn = 0;
    for(int i = 2;i<=N;i++)
    {
        int tmp = i,ans = 1;
        for(int j = 1;j <= 10;j++)
        {
            int cnt = 0;
            while(tmp % prime[j] == 0)
            {
               tmp /= prime[j];
               cnt++;
            }
            ans *= (cnt+1);
            if(tmp == 1) break;
        }
        if(ans > maxn)
        {
            cout<<i<<endl;
            maxn = ans ;
        }
    }
}
int main ()
{
    solve();
    return 0 ;
}
#include<bits/stdc++.h>
using namespace std;
int a[] = {1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,
332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,
4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,
36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,735134400,1102701600
,1396755360};
int main()
{
    int n;
    cin>>n;
    for(int i = 1;i<=67;i++)
    {
       if(n < a[i])
       {
          cout<<a[i-1]<<endl;
          return 0;
       }
    }
    cout<<a[66]<<endl;
    return 0 ;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int prime[] = {0,2,3,5,7,11,13,17,19,23,29,31};
int maxsum = 0;
int ans = 0;
int n;
void dfs(int now,int sum,int k)
{
    if(sum > maxsum)//当前因子个数大于最大值时，更新最大值见性质1
    {
        maxsum = sum;
        ans = now;
    }
    if(sum == maxsum && ans > now) ans = now;//因子个数相等时，使此时的数尽量小见性质2
    if(k > 11) return ;//深度大于11时 return
    for(int i =1;i<=31;i++)//2^31大于2e9
    {
        if(n / prime[k] < now) return ;//当前值乘上因子的值比n大 return
        dfs(now*=prime[k],sum*(i+1),k+1);//搜索下一个状态
    }
}
int main ()
{
    cin>>n;
    dfs(1,1,1);
    cout<<ans<<endl;
    return 0 ;
}

例题 3
- 题目
  HDU4133
- 题意
- 分析

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int prime[] = {0,2,3,5,7,11,13,17,19,23,29};
int n;
ll ans = 0;
ll maxsum = 0;
void dfs(ll now,ll sum,ll k)
{
   if(sum > maxsum)
   {
      maxsum = sum;
      ans = now;
   }
   if(sum == maxsum && ans > now)
   {
     ans = now;
   }
   if(k > 10) return ;
   ll tmp = now;
   for(int i = 1;i <= 31;i++)
    {
        if(n / prime[k] < tmp) return ;
        dfs(tmp*=prime[k],sum*(i+1),k+1);
    }
}
int main ()
{
    int t;
    cin>>t;
    int flag = 0;
    while(t--)
    {
        cin>>n;
        ans = 0;
        maxsum = 0;
        dfs(1,1,1);
        cout<<"Case #"<<++flag<<":"<<" ";
        cout<<ans<<endl;
    }
    return 0 ;
}

例题 4
- 题目
  HDU2531
- 题意
- 分析
  神坑，跟反素数没有半点关系。就是暴力算就可以了

#include<bits/stdc++.h>
using namespace std;
int prime[]={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int maxsum = 0;
int ans = 0;
int a,b;
void dfs(int now,int k,int sum)
{
    if(sum > maxsum && now >= a)
    {
        maxsum = sum;
        ans = now;
    }
    if(sum == maxsum && ans > now && now >= a)
        ans = now;
    if(k > 8) return ;
    int tmp = now;
    for(int i = 1;;i++)
    {
        if(b/prime[k] < tmp) return ;
        dfs(tmp*=prime[k],k+1,sum*(i+1));
    }
}
int main ()
{
    int t;
    cin>>t;
    while(t--)
    {
        maxsum = 0;
        ans = 0;
        cin>>a>>b;
        dfs(1,1,1);
        if(a == b) ans = a;
        cout<<ans<<endl;
    }
    return 0 ;
}

暴力

#include<bits/stdc++.h>
using namespace std;
const int prime[] = {0,2,3,5,7,11,13,17,19};
int solve(int x)
{
    int m = 0;
    for(int i = 1;i <= sqrt(x);i++)
    {
        if(x % i == 0)
        {
            if(x / i == i) m ++;
            else m += 2;
        }
    }
    return m;
}
int main ()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
        int ans = 0;
        int maxn = 0;
        for(int i = a ;i<=b;i++)
        {
            if(solve(i) > maxn)
            {
                maxn = solve(i);
                ans = i;
            }
            if(solve(i) == maxn && ans > i)
            {
                ans = i;
            }
        }
        cout<<ans<<endl;
    }
    return 0 ;
}

例题 5
- 题目
  ZOJ2562
- 题意
- 分析
  反素数裸题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll maxsum = 0;
ll ans = 0;
ll n;
const int prime[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43};
void dfs(ll now,ll sum,ll k)
{
    if(sum > maxsum)
    {
        maxsum = sum;
        ans = now;
    }
    if(sum == maxsum && ans > now)
       ans = now;
    if(k > 16) return ;
    ll tmp = now;
    for(int i= 1;i<=63;i++)
    {
        if(n /prime[k] < tmp) return ;
        dfs(tmp*=prime[k],sum*(i+1),k+1);
    }
}
int main ()
{
    while(scanf("%lld",&n)!=EOF)
    {
        maxsum = 0;
        ans = 0;
        dfs(1,1,1);
        cout<<ans<<endl;
    }
    return 0 ;
}

例题 6：
- 题目
  HDU4542
- 题意
- 分析
  $0$ 操作反素数
  $1$ 操作巧妙的预处理，类似于埃氏筛。==重要的思想==

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int prime[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
const ll INF = ((ll)1<<62)+1;
const int N = 50005;
ll ans;
ll d[N];
int op,n;
void dfs(ll dep,ll tmp,ll num,int lim)
{
    if(num > n) return ;
    if(num == n && ans > tmp) ans = tmp;
    if(dep > 16) return ;
    for(int i = 1;i<=lim;i++)
    {
        if(ans / prime[dep] < tmp || num*(i+1) > n) return;
        tmp *= prime[dep];
        if(n % (num*(i+1)) == 0)
        dfs(dep+1,tmp,num*(i+1),i);
    }
}

void Init()
{
    for(int i=1;i<N;i++) d[i] = i;//1~i中与i互质的数最多有i个
    for(int i=1;i<N;i++)
    {
        for(int j=i;j<N;j+=i) d[j]--;//i是j的一个因数，那么j中的与j互质的数就会减少一个
        if(!d[d[i]]) d[d[i]] = i;//模拟结果显示此时的d[i]表示为1~i中不是i的因数的个数即：k
        //当d[d[i]]等于0时表示还没有构成映射，将此时的i和k构成映射,第一次形成的映射是i是最小的。
        //当d[d[i]]不等于0时表示已经有i和k构成映射了，且它的i更小
        d[i] = 0;//d[i]已经使用过了d[i]的数据对后面的操作不影响，设置成0是为了之后的判断，如果不设成0的话，会让之后的某些数认为k值已经更新过了，导致设置的答案错误。
    }
}
int main ()
{
    int t;
    cin>>t;
    int flag = 0;
    Init();
    while(t--)
    {
        cin>>op>>n;
        if(op == 0)
        {
            ans = INF;
            dfs(1,1,1,63);
        }
        else
        {
            ans = d[n];
        }
        printf("Case %d: ",++flag);
        if(ans == 0) puts("Illegal");
        else if(ans >= INF) puts("INF");
        else printf("%lld\n",ans);

    }
    return 0 ;
}

反素数研究

反素数研究

猜你喜欢

热点阅读