当前位置:编程学习 > C/C++ >>

hdu4279 Number-------天津网络赛 打表找规律

Number
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 492    Accepted Submission(s): 159


Problem Description
  Here are two numbers A and B (0 < A <= B). If B cannot be divisible by A, and A and B are not co-prime numbers, we define A as a special number of B.
  For each x, f(x) equals to the amount of x’s special numbers.
  For example, f(6)=1, because 6 only have one special number which is 4. And f(12)=3, its special numbers are 8,9,10.
  When f(x) is odd, we consider x as a real number.
  Now given 2 integers x and y, your job is to calculate how many real numbers are between them.

Input
  In the first line there is an integer T (T <= 2000), indicates the number of test cases. Then T line follows, each line contains two integers x and y (1 <= x <= y <= 2^63-1) separated by a single space.

Output
  Output the total number of real numbers.

Sample Input
2
1 1
1 10

Sample Output
0
4
Hint
 For the second case, the real numbers are 6,8,9,10.
 

Source
2012 ACM/ICPC Asia Regional Tianjin Online

Recommend
liuyiding
比赛的时候真是把神经绷得太紧了。
打表代码
[cpp] 
#include<iostream> 
#include<cstdlib> 
#include<stdio.h> 
#include<math.h> 
using namespace std; 
#define ll  __int64 
ll a[110]; 
int main() 

    a[1]=0; 
    for(int i=2;i<=50;i++) 
    { 
        int count=0; 
        for(int j=2;j<i;j++) 
        { 
            if(i%j==0) continue; 
            bool flag=false; 
            for(int k=2;k<j;k++) 
            { 
                if(j%k==0&&i%k==0) 
                { 
                    flag=true;break; 
                } 
            } 
            if(flag&&(i%j!=0)) { 
               // cout<<i<<" "<<j<<"*"<<endl; 
                count++; 
            } 
        } 
        if(count&1) a[i]=a[i-1]+1; 
        else a[i]=a[i-1]; 
        cout<<i<<" "<<a[i]<<endl; 
    } 

规律:long long xx = (long long)sqrt(x * 1.0);    if(xx & 1)    {        return ((x - 4) >> 1) + 1;    }    else    {        return ((x - 4) >> 1);    }

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,