Description

正整数$x$ 的约数是能整除$x$ 的正整数。正整数$x$的约数个数记为$div(x)$。例如，$1,2,5,10$ 都是正整数$10$的约数，且$div(10)=4$。设$a$ 和$b$是$2$ 个正整数，$a≤b$，找出$a$和$b$之间约数个数最多的数$x$。对于给定的$2$个正整数$a≤b$，计算$a$ 和$b$之间约数个数最多的数。

Input

输入数据的第$1$行有$2$个正整数$a$和$b$，$a≤1000000000$,$b≤1000000000$。

Output

若找到的$a$和$b$之间约数个数最多的数是$x$，将$div(x)$输出。

Sample Input

1 36

Sample Output

9

问题分析

题目求区间$[a,b]$之间约数个数最大的结果,由于后半部分的数更有可能成为候选结果,可通过$O(\sqrt{n})$的复杂度求出一个数的约数个数,取约数个数最大的一个即可.

官方题解

代码实现

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

typedef long long ll;

ll a,b;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> a >> b;
    /*if(a>b)
        swap(a,b);*/
    ll maxx=1;
    for(ll i=a;i<=b;i++)
    {
        if(i*2<=b)
            continue;
        else
        {
            ll cnt=0;
            for(ll j=1;j<=sqrt(i);j++)
            {
                if(i%j==0)
                    cnt+=2;
                if(j*j==i)
                    cnt--;
            }
            maxx=max(maxx,cnt);
        }
    }
    cout << maxx << endl;
    return 0;
}