Luogu P1463 [HAOI2007]反素数ant：数学 + dfs【反素数】

题目链接：https://www.luogu.org/problemnew/show/P1463

题意：

　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。

　　如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。

　　现在给定一个数N，你能求出不超过N的最大的反质数么？

题解：

　　对于一个反素数p有两个结论：

　　　　若将p表示为 ∏(a[i]^k[i])的形式，其中a[i]为质因子，k[i]为指数。

　　　　（1）a[i]为从2开始的连续质数：2,3,5,7...

　　　　（2）k[i]为不升序列：k[1]>=k[2]>=...k[x]

　　证明：

　　　　结论1：

　　　　　　因为一个数x的因子个数 = ∏(k[i]+1)

　　　　　　所以当两个数的k[i]序列完全相同时，a[i]为从2开始的连续质数的那个数字更小。

　　　　　　所以另一个数一定不是反素数。

　　　　结论2：

　　　　　　若两个数的k[i]序列的元素相同（如{1,1,2}和{1,2,1}相同）

　　　　　　由结论1可知，两个数的a[i]序列完全相同（都是从2开始的连续质数）

　　　　　　所以k[i]为不升序列的那个数一定更小。

　　　　　　所以另一个数一定不是反素数。

　　那么就可以爆搜了。

　　在保证a[i]为从2开始连续质数，且k[i]不升的前提下，枚举n以内所有可能是反素数的数。

　　在枚举出的所有数中，答案为因子个数最多的那个数。

　　若有因子相同的多个数，则选最小的那个数。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define INF 1000000000

 using namespace std;

 const int p[]={,,,,,,,,,,,,,,,,};

 long long n;

 long long ans=;

 long long now=;

 void dfs(int x,int lst,long long tot,long long v)

 {

     if(tot>now || (tot==now && v<ans)) ans=v,now=tot;

     int cnt=;

     while(v*p[x]<=n && cnt<lst)

     {

         v*=p[x]; cnt++;

         dfs(x+,cnt,tot*(cnt+),v);

     }

 }

 int main()

 {

     cin>>n;

     dfs(,INF,,);

     cout<<ans<<endl;

 }

巴特西

Luogu P1463 [HAOI2007]反素数ant：数学 + dfs【反素数】

最新文章

热门文章