boj 1344 複雜數問題

位址： http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1344

1.對這類題，先選取他們的和 2*3*5*7*11*13=30030  數字是按規律出現的，每30030一個周期。

2.對字元串裡的數字變成整形，temp=temp*10+a[i]-'0';

3.對某數取模，可以按上面的方法一位一位取模~

Description

Sunny認為，1和任何能被2，3，5，7，11，13之一整除的正整數都是簡單數，其他的都是複雜數，比如4，15，169是簡單數，而19，29，289都是複雜數。

求從x開始的（包括x）後k個數中（即從x到x+k-1）有多少個複雜數？

Input

第一行 n，表示有n個case。

之後每一個case一行，分别有兩個正整數，x（x<10^100000），k（k<2^30）。

Output

每行一個結果。

Sample Input

3

3 20

23 1

24 5

Sample Output

2

1

Source

#include<iostream>

#include<string.h>

using namespace std;

char a[100010];

int b[30031];

int main()

{

    int i,n,x,temp,count,l,m;

    long int k;

    b[0]=0;

    for(i=1;i<30030;i++)

    {

      b[i]=b[i-1]+(i%2!=0 && i%3!=0 && i%5!=0 && i%7!=0 && i%11!=0 && i%13!=0);                

                        }

    scanf("%d",&n);

    while(n--)

    {

       temp=0;

       scanf("%s %ld",a,&k);

       k--;

       l=strlen(a);

       for(i=0;i<l;i++)

         temp=(temp*10+a[i]-'0')%30030;  //一個數的對某數的模，等于一位一位取模後得到的數。

       m=k/30030;

       m=m+(temp+k%30030)/30030;

       count=b[(temp+k%30030)%30030]+b[30030-1]*m-b[(temp+30030-1)%30030];     //分别為n-k的  如果k>30030那麼有k/30030個30030的 

       printf("%d/n",count);                                                   //還要減去 0-n的

              }

              system("pause");

    }