0

我正在解决一个问题。
问题链接：

http://www.codechef.com/NOV13/problems/PRETNUM

问题是关于在 L 和 R 的给定范围内计算除数素数的数字（除数素数的数字）。 1<=L<=R<=10^12 和 LR<=10^6

我的代码为小于 10^10 的输入提供了正确的输出。但是对于大于 10^10 的数字，答案要么比正确答案小 1，要么比正确答案大 1。我无法弄清楚问题可能是什么。我的解决方案：

/*
*   Problem link: http://www.codechef.com/NOV13/problems/PRETNUM
*   Approach: Using Segmented Sieve to generate primes, and counting divisors
*             for perfect squares.
*   Abhishek Kannojia
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PLIMIT 78500
#define NLIMIT 1000000
typedef unsigned long long int  ull;

int primes[PLIMIT], maxp;


//Precomputing Pirmes upto 10^6
int precompute() {
unsigned long i, j, k;
int *numbers;

numbers=(int *)malloc(sizeof(int)*NLIMIT+2);

    for(i=2; i<NLIMIT; i++)
        numbers[i]=1;

    //Sieving Primes
    for(i=2; i<=NLIMIT; i++) {
        if(numbers[i]) {
                for (j=i+i;j<=NLIMIT;j+=i) {
                numbers[j]=0;
            }
        }
    }
    k=0;//printf("\nGenerated Prime:\n");
    for(i=2; i<NLIMIT; i++)
        if(numbers[i]) {primes[k++]=i; /*printf("%d\n",i);*/}

    free(numbers);

    return k;
}

int isprime(int n)
{
 int i=0;
 if(n==0) return 0;
 for(i=0; i<=maxp; i++) {
    if(primes[i]==n) return 1;
 }
 return 0;
}

// Counting Number of Divisors based on the fact that
// if prime factorisation of n = (p)^a * (q)^b * (r)^c
// then number of divisors will be (a+1)*(b+1)*(c+1)

int divcount(ull num)
{
 int i=0, count=1, n, power;

 if(num==1) return 0;
 while(num>1 && i<maxp) {
   n=primes[i];
   power=0;
   while(num%n==0) {
     num /= n;
     power++;
   }
   count = count*(power+1);
   i++;
 }

//
//  This case handles when on of the prime factor is greater than 10^6
//  which does not fall in precomputed array. But we are sure that only
//  one such prime exists for (n<10^12). So we mulitply result by (1+1)
//

 if(num>1) count*=2;
 return count;
}

int calculate(ull l, ull r)
{
  int i, j, k, n, m, count=0, *numbers;
  ull p;

  m=ceil(sqrt(l));
  n=floor(sqrt(r));

    // If l and r less than 10^6. Directly count from precomputed array.
    // The count of divisor is only checked for perfect squares.

  if(r<=NLIMIT) {
    for(i=0; primes[i]<=r; i++) {
        if(primes[i]>=l) count++;
    }
    while(m<=n) {
        if(isprime(divcount(m*m))) count++;
        m++;
    }
  }
  else {
    for(i=0; i<maxp; i++) if(primes[i]>=l) count++;

    for(i=0; i<maxp;) if(primes[i++]>=r) break;
    k=i;

    // Sieving primes Using Segmented Sieve

    numbers = (int *)malloc(sizeof(int)*(r-l+1));

    i=0;
    for(p=l; p<=r; p++) numbers[i++]=1;
    n=i;

    for(i=0; i<k; i++) {
        if(l%primes[i]==0) j=0;
        else j=primes[i]-(l%primes[i]);
            for(;j<n; j+=primes[i]) {
                if(numbers[j]) {
                    numbers[j]=0;
                }
            }

    }
    for(i=0; i<n; i++)
       if(numbers[i]) count++;

    n=sqrt(r);
    while(m<=n) {
        if(isprime(divcount(m*m))==1) count++;
        m++;
    }
 }
 return count;
}

int main(){

    int tc, i, c;
    ull l, r;
    maxp=precompute();
    scanf("%d",&tc);
    while(tc--)
    {
        scanf("%llu %llu",&l,&r);

    c=calculate(l,r);
    printf("%d\n",c);
    }
  return 0;
}

我的方法是首先计算给定范围内的所有素数（因为它们的除数为 2，这是素数），然后检查范围内完美平方的除数，因为只有完美的平方才能有素数除数。

为了计算素数，我使用了分段筛法。为了计算完美平方的除数，我使用了这样一个事实：如果一个数 N 具有素因数分解 N = (p)^a * (q)^b * (r)^c 那么 N 的除数将是 (a+1 ) (b+1) (c+1) [ https://stackoverflow.com/a/110365 ]

谁能帮我这个..

4

1 回答 1

1

您正在使用无符号长类型。它对于 10^10 来说不够大。无符号长整数是从 0 到 4294967295 (2^32 - 1)。它小于 5 * 10^9。所以你必须使用更大的内部类型（64 位）或长算法（你自己的整数数据类型的实现）。

于 2013-11-19T05:48:36.483 回答