A、Magic Number
题目大意:一个数y能够被称为Magic Number需满足对于任意正整数x,将y放在x的右边,构成新数z,满足z%y==0.
输入:m,n
输出:m与n之间Magic Number数的个数(包含m和n)
解题思路:打部分表之后找规律,在10以内满足条件的为:1,2,5;在10~100之间,满足条件的为10,20,25,50;在100~1000之间,满足条件的为100,125,200,250,500;在这之后的每一个10倍均有5个数满足条件。

#include <stdio.h>
#define intt  long long
int main(){
    intt n[2];
    intt num[20]={1,2,5,10,20,25,50,100,125,200,250,500};
    while(scanf(“%lld%lld”,&n[0],&n[1])!=EOF){
        intt sum[2],i,j;
        n[0] –;
        for(i=0;i<2;i++){
            sum[i]=0;
            while(n[i]>=1000){
                sum[i]+=5;
                n[i]/=10;
            }
            for(j=0;j<12;j++)
                if(n[i]>=num[j])
                    sum[i]++;
        }
        printf(“%lld\n”,sum[1]-sum[0]);
    }
    return 0;
}

H、Treasure Hunt IV
题目大意:对于任意一个非负整数x,都有一个值f(x)=[x/1]+[x/2]+…+[x/k]+…(k>=1 && k<=n因为当k>n后,[n/k]恒为0);x被称为real number当且仅当f(x)为偶数;否则为fake number
输入:m,n
输出:m与n之间的所有real number的个数(包含m和n)
解题思路:打部分表找规律,发现real number的个数从0开始成首项为1,公差为4的等差数列
x  f(x)
0   0   ——1(real)
   1   1
2   1
3   1   ——3(fake)
4   0
5   0
6   0
7   0
8   0  ——5(r)
9   1
10   1
11   1
12   1
13   1
14   1
15   1  ——7(f)
16   0
17   0
18   0
19   0
20   0
21   0
22   0
23   0
24   0 ——9(r)
25   1
26   1
27   1
28   1
29   1
30   1
31   1
32   1
33   1
34   1
35   1 ——11(f)
36   0
37   0
38   0
39   0
40   0
41   0
42   0
43   0
44   0
45   0
46   0
47   0
48   0 ——13(r)
49   1
50   1
…    …

#include <stdio.h>
#include <math.h>
#define intt long long

intt solve(intt n){
    intt a=(intt)sqrt(n);
    intt sum;
    if(n==-1)
        return 0;
    if(a%2==0){          //如果sqrt(n)为偶数,说明n就在一个real number数列中
        sum=n-a*a+1; //所在real number列的real个数
        a-=2;                      //a-2之前的所有real number列就全部包含了
    }
    else{                          //如果sqrt(n)为奇数,说明n在一个fake number数列中
        sum=0;               //所在fake number列的real个数为0
        a–;                          //a-1之前的所有real number列就全部包含了
    }
    a/=2;                         //Sn=n*a1+n*(n-1)*d/2
    a++;                           //首项为1
    return sum+2*a*a-a;          //a1=1,d=4
}
int main(){
    intt n,m;
    while(scanf(“%lld%lld”,&n,&m)!=EOF){
        intt a=solve(n-1);
        intt b=solve(m);
        printf(“%lld\n”,b-a);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation