题解 UVA294 【约数 Divisors】

Froggy · 2019-06-07 20:23:00 · 题解

约数个数定理裸题

约数个数定理:

设 n=\prod^k_{i=1}p_{i}^{q_{i}}

则n的约数个数 f(n)=\prod^k_{i=1}(q_{i}+1)

举个例子:

此题做法::

1.先把\sqrt{r}内的所有质数筛出来,(线筛埃筛自己选)

代码:

//我用线筛
int primes[N],pn=0;
bool nt_p[N];
void get_primes(){
    nt_p[1]=true;
    for(int i=2;i<=35000;i++){
        if(!nt_p[i])primes[++pn]=i;
        for(int j=1;j<=pn&&i*primes[j]<=35000;j++){
            nt_p[i*primes[j]]=true;
            if(i%primes[j]==0)break;
        }
    }
}

2.求出l~r内的f(i)

代码:

//把x分解了就行
ll get_factor(ll x){
    ll ans=1;
    for(int i=1;i<=pn;i++){
        if(primes[i]>x)break;
        int cnt=1;
        while(x%primes[i]==0){
            cnt++;
            x/=primes[i];
        }
        ans*=cnt;
    }
    return ans;
}

3.呃呃呃,发现题做完了,不就是求最大的f(i)么? 直接输出喽~~

输出真tm长

全部代码:

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
#define N 37000
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int T,primes[N],pn=0;
ll l,r,ans,msum;
bool nt_p[N];
void get_primes(){
    nt_p[1]=true;
    for(int i=2;i<=35000;i++){
        if(!nt_p[i])primes[++pn]=i;
        for(int j=1;j<=pn&&i*primes[j]<=35000;j++){
            nt_p[i*primes[j]]=true;
            if(i%primes[j]==0)break;
        }
    }
}
ll get_factor(ll x){
    ll ans=1;
    for(int i=1;i<=pn;i++){
        if(primes[i]>x)break;
        int cnt=1;
        while(x%primes[i]==0){
            cnt++;
            x/=primes[i];
        }
        ans*=cnt;
    }
    return ans;
}
int main(){
    get_primes();
    T=read();
    while(T--){
        l=read(),r=read();
        ans=0,msum=0;
        for(ll i=l;i<=r;i++){
            ll isum=get_factor(i);
            if(isum>msum){
                ans=i,msum=isum;
            }
        }
        cout<<"Between "<<l<<" and "<<r<<", "<<ans<<" has a maximum of "<<msum<<" divisors."<<endl;
    }
    return 0;
}

时间复杂度:O(T(r-l)\sqrt{r}/In(\sqrt{r}))