“玲珑杯”ACM比賽 Round #9 A -- Check-in Problem [因子個數]【數論】

題目連接配接: http://www.ifrog.cc/acm/problem/1084

———————————————————————————————————-. 

A – Check-in Problem 

Time Limit：5s Memory Limit：128MByte

Submissions：921 Solved：55

DESCRIPTION

A positive integer x is called p-bizarre number if the number of the divisors of x is p exactly. 

Your task is testing whether the given positive integer n is a p-bizarre number or not.

INPUT

The first line contains a positive integer T, which represents there are T test cases. 

The following is test cases. For each test case: 

The only one line contains a positive integer n and an odd prime p. 

1≤T≤10^5,1≤n≤10^18,2< p≤10^9

OUTPUT

For each test case, output in one line, print “YES” (without quote) if n is a p-bizarre number, print “NO” (without quote) otherwise.

SAMPLE INPUT

3 

9 3 

971528476274196481 7 

150094635296999121 37

SAMPLE OUTPUT 

YES 

NO 

YES 

———————————————————————————————————-. 

題目大意: 

就是問你n的因子個數是不是p個

解題思路: 

對于一個素數n的因子個數 我們可以對n做算術基本定理展開 

n=pa11×pa22×pa33×...×parr

那麼數的因子個數就是  ∑ri=1(a1+1)×(a2+1)×(a3+1)×...×(an+1)

input裡面又說 

The only one line contains a positive integer n and an odd prime p.

那麼對于p是素數的情況 隻能說明n的質因子隻有一種,

因為上述,是以我想到以對1e6(因為題目說p最小是3,n最大是10^18,是以1e6就夠了)内的素數篩法取一遍,然後二分尋找答案即可注意會爆LL ,但是無論怎麼控制溢出,最後代碼寫成了這樣但是還是WA…心塞…

獻上官方題解

注意到 p  是質數，隻有當  n  是質數的  p−1 次幂時，  n  的約數才可能恰好有  p  個，是以判定一個正整數  n  是  p− 奇異數，隻需檢驗  p−1n√  是整數，且  p−1n√  是質數。預處理  109−−−√  以内的素數（共  3401  個），進行開根和判斷素數即可，時間複雜度 O(n√lnn) 。 

事實上  p>3  的情況很少有解，直接預處理所有有解的情況即可，可以防止寫出有問題的開根，而  p=3  的判斷素數也可以用 Miller-Rabin 算法判定（需要  O(1)  的模乘法）。

改了2個小時的溢出，最後都沒簽到。。。。。。

獻上标程一枚 

———————————————————————————————————-.

#include <cmath>
#include <stdio.h>
#include <cassert>
#include <algorithm>
typedef long long LL;
const int maxn = , maxm = , maxp = , maxt = , maxv2 = (int);
const LL maxv = (LL);
int tot, pr[maxn], d[maxn], sz[maxm];
LL pp[maxm][maxn];
bool isprime(int x)
{
    if(x < )    return ;
    if(x < maxn) return d[x] == x;
    for(int i = ; i < tot && pr[i] * pr[i] <= x; ++i)
        if(x % pr[i] == )  return ;
    return ;
}
int main()
{
    for(int i = ; i < maxn; ++i)
    {
        if(!d[i])
            pr[tot++] = d[i] = i;
        for(int j = , k; (k = i * pr[j]) < maxn; ++j)
        {
            d[k] = pr[j];
            if(d[i] == pr[j])break;
        }
    }

    for(int i = ; i < maxm; ++i)
        for(int j = ; j < tot; ++j)
        {
            int rem = pr[i] - ;
            LL val = , lim = maxv / pr[j];
            for( ; rem && val <= lim; --rem, val *= pr[j]);
            if(rem)     break;
            pp[i][sz[i]++] = val;
        }

    int t;
    LL n, p;
    assert(scanf("%d", &t) == 
    &&  <= t && t < maxt);
    while(t--)
    {
        assert(scanf("%lld%lld", &n, &p) == 
        &&  <= n && n <= maxv
        && (p & ) && p <= maxv2 && isprime(p));
        if(p >= maxp || d[p] != p)
        {
            puts("NO");
            continue;
        }
        if(p == )
        {
            LL val = (LL)sqrt(n);
            for( ; val * val > n; --val);
            for( ; (val + ) * (val + ) <= n; ++val);
            puts(val * val == n && isprime(val) ? "YES" : "NO");
            continue;
        }
        for(int i = ; i < maxm; ++i)
            if(pr[i] == p)
            {
                puts(*std::lower_bound(pp[i], pp[i] + sz[i], n) == n ? "YES" : "NO");
                break;
            }
    }
    return ;
}
           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72