首页 > ACM题库 > HDU-杭电 > hdu 1923 Exploding CPU-数论[解题报告]C++
2013
12-26

hdu 1923 Exploding CPU-数论[解题报告]C++

Exploding CPU

问题描述 :

The well known hardware manufacturing company Processors for Professors is about to release a highly specialized CPU with exceptional functionality in, amongst other areas, number theory. It has, for example, an instruction PFACT that takes one parameter and returns all prime factors of that parameter, with an outstanding execution speed. It has, however, one considerable problem. The scientists at the testing lab has just found out that the PFACT instruction for some special input values freaks out and makes the entire processor explode. Even though this could be an amusing effect, it is not the way it was intended to work. The skilled mathematicians have, by trial and error, found that the explosive numbers all share the same interesting number theoretic properties, which might be of help when troubleshooting.An explosive number is a number where all s are distinct prime numbers such that . A and B are always integers, and might be different for different explosive numbers.

For example, the processor will explode when factorizing the number 4505, because 4505 = 1*5*17*53 and 5 = 3*1+2, 17 = 3*5+2 and 53 = 3*17+2 and the numbers 5, 17 and 53 are all prime numbers. In this case A = 3 and B = 2.

You are kindly asked to write a computer program that will aid this company in estimating the impact of the errors, by calculating the amount of explosive numbers that exists within a given range of integers.

输入:

The input starts with a row containing the number 0 <= N <= 100 of test cases that will follow. For each test case, there will be one row containing two integers, separated by a single space. These numbers are such that .

输出:

The input starts with a row containing the number 0 <= N <= 100 of test cases that will follow. For each test case, there will be one row containing two integers, separated by a single space. These numbers are such that .

样例输入:

2
4505 4505
0 5000

样例输出:

1
5


呵呵 过了这个题目挺高兴
锻炼了 筛法和判断素数的能力
还想了一个关键的枚举剪枝
这个题目我是去枚举题目中的A和第一个素数P1;
然后计算B 幷继续推Pn
对小于1000000的数一次性筛出;
大数用最基本的判断的方式。

#include<stdio.h>
#include<math.h>
#define SSS 6000
#define SIZE 1000000
#define INF 2000000000
#define NUM 200
__int64 aa[300];
__int64 rr[50000];
int pri[NUM];
int sub[SIZE];
int pdsu(__int64 n)
{
    __int64 i;
    if(n<=0||n==1 )
        return 0;
    if( n==2)
        return 1;
    else{
        for(i=2; i*i<=n; i++)
            if(n%i==0)
                return 0;
    }
    return 1;
}
void sf(){
    int temp,n;
    for(int i=0;i<SIZE;i++)
       sub[i]=1;
    sub[0]=sub[1]=0;
    for(int i=2;i<=sqrt(SIZE);i++){
        if(sub[i]==1){
           temp=2*i;
           while(temp<=SIZE){
                 sub[temp]=0;
                 temp+=i;
           }
        }
    }
}
int  init(){
      int j = 0 ;
      pri[j++] = 2 ;
      pri[j++] = 3 ;
      for( int i = 3 ; i<SSS ;i++ ){
         if(sub[i]){
                     pri[j++]=i;
         }
      }
      return j;
}
int main(){
    int num;
    int t = 0 ;
    __int64 res , next ,next2 ;
  int b;
  sf();
    num = init();
  sf();
               for(int a = 1 ; a< 600 ; a++ ){
                       for(int i = 0; i<NUM ;i++  ){
                              res = pri[i] ;
                              b = pri[i] - a;
                              if(b == 0 ) continue;
                              next = a * pri[i] + b ;
                              if(next == pri[i]) continue;
                              if(res * next > INF){
                                      continue;
                                      }
                              if(next <0 )
                                      continue;
                              if(next >= SIZE){
                                  if(!pdsu(next))
                                      continue ;
                              }
                             else{
                                      if(!sub[next])
                                      continue ;
                              }
                              res = res * next;
                              if(res >INF) continue;

                            while(1){
                               next2 = next * a +b;
                               if(next2 == next ) break;
                               if(res * next2 > INF){
                                      break;
                                      }
                               if(next2 <0 )
                                      break;
                             if(next2 >= SIZE){
                                      if(!pdsu(next2))
                                      break ;
                              }
                              else{
                                      if(!sub[next2])
                                      break ;
                              }
                              res = res * next2;
                              if(res >INF) break;
                              rr[t++] = res ;
                              next = next2 ;

                            }

                       }
               }

     for(int i = 0 ; i<t ;i++ )
             for(int j = i+1 ; j <t ;j++)
                     {
                         if(rr[i]>rr[j]){
                         int temp = rr[i];
                         rr[i] = rr[j];
                         rr[j] = temp;
                         }

                     }
       int ccc = 0;
      for(int i = 0 ; i <t ; i++)
     {
              if(rr[i]!= rr[i+1])
              aa[ccc++]=rr[i];
     }
  //    printf("init over\n");
     int N;
    __int64 zuo ,you ;
            scanf("%d",&N);
               while(N--){
               scanf("%I64d%I64d",&zuo,&you);

          int     ans = 0 ;
         for(int i = 0 ; i <243 ;i++){
                 if(zuo<=aa[i] && you>=aa[i])
                ans++;
         }
               printf("%d\n",ans);
               }
    return 0 ;
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }