约数个数问题:
1.1-n中的约数个数：
1.怎么求个数：分解质因子后
(c1+1)(c2+1）...
2.估算复杂度：1-n当中有每个数中的约数个数和
N/1+N/2+.. 总共是nlogn个
3.0-2e9 最多的约数个数是1600个数

T2

• 数论题目本身就需要对式子进行一定的推导
• 对于二元问题，我们转化成y=f(x)的形式
• 进而问题变成：对于多少个x，有等式成立并y满足题目条件（正，整数）
• 根据枚举的思路，分子分母中只出现一个x才好枚举
• 如果最后缺乏条件，不妨回到原本的式子当中寻找
• 最后得出是求n！^2的约束

求n!的约数个数：

• 对于求这个，转化思想，变成每一个质数对于他的倍数有多大的贡献（乘法容易取模难）
• 每次从n开始，寻找一共有多少个数是含有k个p的
• 核心代码：for(int j=n;j;j/=p) s+=j/p;

T3
转化思路：约数个数最多的最小的数

• 1.不同的质因子的个数数很小的<9
• 2.每个质因子的次数小于30
• 3.所有质因子的次数是递减的：小的先填
• 数论优先思想【可以手算来先确定一下数据范围】
• 2147483647(2^32-1）

#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;
#define ll long long
int prime[9]={2,3,5,7,11,13,17,19,23};
int n;
int maxd,num;

inline void dfs(int j,int ci,int p,int yue)
{
    if(yue>maxd||(yue==maxd&&p<num))
    {
        num=p;
        maxd=yue;
    }
    if(j==9) return;//
    for(int i=1;i<=ci;i++)
    {
        if((ll)p*prime[j]>n) break;//此处考虑爆int 开ll
        p*=prime[j];
        dfs(j+1,i,p,yue*(i+1));
    }
    return;
}
int main()
{
    scanf("%d",&n);
    dfs(0,30,1,1);//从1开始
    printf("%d",num);
    return 0;
}

View Code

注意一下爆搜的写法：

• 1.明确搜索顺序（质数从小到大）->搜索边界(u==9）
• 明确含参数：上一个的次数，当前枚举的个数，当前的乘积（防止爆炸）(prime*p>n),当前约数个数
• 更新答案:（yue>maxd||yue==maxd&&p<num）
• 更新过程：枚举次数 1->ci就

T4hanson的趣味题

• (a,x）=b [c,x]=d求1-n当中有多少的n是满足的
• 分析题目，二元条件转验证，枚举x需要找范围
• 发现x是d的约数，所以转为找d的约数
• 发现枚举需要根号n；
• 根据思想：质因子的个数是很少的(x/lnx）所以考虑分解质因子，优化10倍
• 

  #include <stdio.h>
  #include <algorithm>
  #include <cstring>
  #define ll long long
  using namespace std;
  
  const int maxn=50010;
  
  int prime[maxn],cnt;
  bool st[maxn];
  int n;
  
  struct Factor
  {
      int p,s;
  }f[1600];
  int fcnt;
  int dive[maxn],dcnt;
  
  inline void init(int n)
  {
      for(int i=2;i<=n;i++)
      {
          if(!st[i]) prime[cnt++]=i;
          for(int j=0;prime[j]*i<=n;j++)
          {
              st[prime[j]*i]=true;
              if(i%prime[j]==0) break;        
          }
      }
  }
  inline int gcd(int a,int b)
  {
      if(b==0) return a;
      else return gcd(b,a%b);
  }
  inline void dfs(int u,int p)
  {
      if(u==fcnt) 
      {
          dive[dcnt++]=p;
          return;
      }
      for(int i=0;i<=f[u].s;i++)//0次方都是可以的
      {
          dfs(u+1,p);
          p*=f[u].p;
      }
      return;
  }
  int main()
  {
      scanf("%d",&n);
      init(maxn-1);
      while(n--)
      {
          int a,b,c,d;
          scanf("%d%d%d%d",&a,&b,&c,&d);
          int t=d;//
          fcnt=0;
          for(int i=0;prime[i]*prime[i]<=d;i++)
          {
              int p=prime[i];
              if(t%p==0) 
              {
                  f[fcnt++].p=p;
                  while(t%p==0) t/=p,f[fcnt].s++;
              }
          }
          if(t>1) f[fcnt++].p=t;f[fcnt].s=1;
          dcnt=0;
          dfs(0,1);
          int res=0;
          for(int i=0;i<dcnt;i++)
          {
              int x=dive[i];
              if(gcd(a,x)==b&&gcd(c,x)==(ll)c*x/d) res++;
          }
          printf("%d\n",res);
      }
      return 0;
  }

  View Code

  #include <stdio.h>
  #include <algorithm>
  #include <cstring>
  #define ll long long
  using namespace std;
  
  const int maxn=50010;
  
  int prime[maxn],cnt;
  bool st[maxn];
  int n;
  
  struct Factor
  {
      int p,s;
  }f[1600];
  int fcnt;
  int dive[maxn],dcnt;
  
  inline void init(int n)
  {
      for(int i=2;i<=n;i++)
      {
          if(!st[i]) prime[cnt++]=i;
          for(int j=0;prime[j]*i<=n;j++)
          {
              st[prime[j]*i]=true;
              if(i%prime[j]==0) break;        
          }
      }
  }
  inline int gcd(int a,int b)
  {
      if(b==0) return a;
      else return gcd(b,a%b);
  }
  inline void dfs(int u,int p)
  {
      if(u==fcnt) 
      {
          dive[dcnt++]=p;
          return;
      }
      for(int i=0;i<=f[u].s;i++)//0次方都是可以的
      {
          dfs(u+1,p);
          p*=f[u].p;
      }
      return;
  }
  int main()
  {
      scanf("%d",&n);
      init(maxn-1);
      while(n--)
      {
          int a,b,c,d;
          scanf("%d%d%d%d",&a,&b,&c,&d);
          int t=d;//
          fcnt=0;
          for(int i=0;prime[i]*prime[i]<=d;i++)
          {
              int p=prime[i];
              int s=0;
              if(t%p==0) while(t%p==0) t/=p,s++;//此处注意
              f[fcnt++]={p,s};
          }
          if(t>1) f[fcnt++]={t,1};
          dcnt=0;
          dfs(0,1);
          int res=0;
          for(int i=0;i<dcnt;i++)
          {
              int x=dive[i];
              if(gcd(a,x)==b&&gcd(c,x)==(ll)c*x/d) res++;
          }
          printf("%d\n",res);
      }
      return 0;
  }

  View Code