HUST 1214 Cubic-free numbers II

Cubic-free numbers II

Time Limit: 10000ms

Memory Limit: 131072KB

This problem will be judged on HUST. Original ID: 1214
64-bit integer IO format: %lld Java class name: Main

A positive integer n is called cubic-free, if it can't be written in this form n = x*x*x*k, while x is a positive integer larger than 1. Now give you two Integers L and R, you should tell me how many cubic-free numbers are there in the range [L, R). Range [L, R) means all the integers x that L <= x < R.

Input

The first line is an integer T (T <= 100) means the number of the test cases. The following T lines are the test cases, for each line there are two integers L and R (L <= R <= ).

Output

For each test case, output one single integer on one line, the number of the cubic-free numbers in the range [L, R).

Sample Input

Sample Output

8

12

67

解题：容斥

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 typedef long long LL;

 LL cnt[maxn],L,R;

 LL calc(LL x) {

     if(x <= ) return ;

     memset(cnt,,sizeof cnt);

     LL i = ;

     for(i = ; i*i*i <= x; ++i)

         cnt[i] = x/(i*i*i);

     for(LL j = i - ; j >= ; --j) {

         for(LL k = j + j; k < i; k += j)

             cnt[j] -= cnt[k];

     }

     LL ret = ;

     for(LL j = ; j < i; ++j)

         ret += cnt[j];

     return ret;

 }

 int main() {

     int kase;

     scanf("%d",&kase);

     while(kase--) {

         scanf("%lld%lld",&L,&R);

         printf("%lld\n",R - L - calc(R - ) + calc(L - ));

     }

     return ;

 }

巴特西