LightOJ - 1341 Aladdin and the Flying Carpet （算术基本定理）

题意：

就是。。。。求a的所有大于b的因子有多少对

算术基本定理求 所有因子 阿欧。。。偷张图。

注意范围 就好  。。。。。

解析：

在1 -10

就等于 在1 -10

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#include<stack>

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long LL;

const int maxn=;

LL primes[maxn], vis[maxn];

LL base[maxn], mi[maxn];

int ans = ;

void init()

{

    mem(vis,);

    for(int i=; i<maxn; i++)

        if(!vis[i])

        {

            primes[ans++] = i;

            for(LL j=(LL)i*i; j<maxn; j+=i)

                vis[j] = ;

        }

}

int main()

{

    int T;

    init();

    int m = ;

    scanf("%d",&T);

    while(T--)

    {

        LL S, edge;

        scanf("%lld%lld",&S,&edge);

        LL x = S;

        if(edge * edge >= S){

            printf("Case %d: 0\n",++m); continue;

        }

        LL res = , cnt2 = ;

        for(int i=; i < ans && primes[i] * primes[i] <= S; i++)

        {

            LL cnt = ;

            while(S % primes[i] == )

            {

                cnt++;

                S /= primes[i];

            }

            if(S > ){

                base[cnt2] = primes[i];

                mi[cnt2++] = cnt;

            }

        }

        if(S > )

        {

            base[cnt2] = S;

            mi[cnt2++] = ;

        }

        LL temp = ;

        for(int i=; i<cnt2; i++)

        {

            res *= (mi[i]+);

            if(base[i] < edge)

                temp *= mi[i];

        }

        printf("Case %d: %lld\n",++m,res/ - temp);

    }

    return ;

}