原创

使用数论中的“唯一分解定理”和“约数定理”

问题描述：正整数x的约数是能整除x的正整数。设a和b是两个正整数，a<=b，找出a和b之间约数个数最多的数x。
输入输出样例：
Input:
1 36
Output:
9

百度词条：关于唯一分解定理
百度词条：关于约数定理
那个，语法没打学会，先就把分析写在纸上拍照了

#include<iostream>
#include<cstdio>
using namespace std;
#define N 10000+10
int A[N],P[N],F[N];
int main()
{
    int ans=1;
    int sta,end1;
    scanf("%d%d",&sta,&end1);
    int cnt=0;
//    for(int i=0;i<=end1;i++)
//    {
//        F[i]=0;
//    }
    for(int i=2;i<=end1;i++)
    {
        if(!F[i])
        {
            P[cnt++]=i;
            F[i]=A[i]=2;
        }
        for(int j=0;j<cnt&&i*P[j]<=end1;j++)
        {
            F[i*P[j]]=2;
            A[i*P[j]]=2*A[i];
            if(i%P[j]==0)
            {
                F[i*P[j]]=F[i]+1;
            A[i*P[j]]=A[i]/F[i]*F[i*P[j]];
              break;
            }
            //cout<<"haha"<<endl;

        }
        if(i>=sta)
            ans=max(A[i],ans);
    }
    cout<<ans<<endl;
}