【算数基本定理(唯一分解定理)】Aladdin and the Flying Carpet LightOJ - 1341

拼搏现实的明天。 2022-06-07 04:59 130阅读 0赞

Think:  
1知识点：算数基本定理(唯一分解定理)  
算术基本定理的几个应用：  
![SouthEast][]  
注：p1, p2, pi都是素数  
同时全体正因数的和也可以写作：  
![SouthEast 1][]  
[——“算数基本定理”参考博客地址][Link 1]

2题意：输入a, b(1 ≤ b ≤ a ≤ 1e12)，a代表一个矩形的面积，b表示矩形中最小的那条边至少长度为b，询问有多少个符合条件的矩形  
注：题意要去本题目中的矩形不是正方形  
3解题思路：  
通过算数基本定理求得a的所有正因数数量，除以2(求解符合情况的矩形)，然后减去所有小于b的正因数的数量  
4反思：  
（1）：判断条件b\*b > a应转化为判断条件b > a/b，进而避免越界  
（2）：通过素数筛得到素数表后，在分解tmp时，可以通过(LL)link\[i\]\*(LL)link\[i\]优化剪枝(未剪枝之前2312ms+,剪枝之后344ms+)

[vjudge题目链接][vjudge]

以下为Accepted代码——344ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int size1 = 1004014;
    
    bool primes[size1];
    int tp, link[size1];
    
    void get_primes();
    
    int main(){
        get_primes();
        int k = 1, T, cnt, num;
        LL a, b, tmp;
        scanf("%d", &T);
        while(T--){
            scanf("%lld %lld", &a, &b);
            if(b >= a/b){
                printf("Case %d: 0\n", k++);
                continue;
            }
            num = 1, tmp = a;
            for(int i = 0; i < tp && (LL)link[i]*(LL)link[i] <= tmp; i++){
                if(tmp%link[i] == 0){
                    cnt = 0;
                    while(tmp%link[i] == 0){
                        cnt++;
                        tmp /= link[i];
                    }
                    num *= (cnt+1);
                }
                if(tmp < link[i]) break;
            }
            if(tmp != 1){
                num <<= 1;
            }
            num >>= 1;
            for(int i = 1; i < b; i++){
                if(a%i == 0) num--;
            }
            printf("Case %d: %d\n", k++, num);
        }
        return 0;
    }
    void get_primes(){
        tp = 0;
        memset(primes, 0, sizeof(primes));
        primes[0] = 1;
        for(LL i = 2; i < size1; i++){
            if(!primes[i]){
                for(LL j = i*i; j < size1; j += i){
                    primes[j] = 1;
                }
                link[tp++] = i;
            }
        }
        return;
    }

[SouthEast]: /images/20220607/298826bdfb584ef3bf34f56c66dbefd3.png
[SouthEast 1]: /images/20220607/c7cd1650d96e48c9bcfdbd6905824f4a.png
[Link 1]: http://blog.csdn.net/codeblocksm/article/details/48318985
[vjudge]: https://vjudge.net/problem/HDU-1238