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.
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 <= ).
For each test case, output one single integer on one line, the number of the cubic-free numbers in the range [L, R).
3 1 10 3 16 20 100
8 12 67
解题：容斥
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 2100000; 4 typedef long long LL; 5 LL cnt[maxn],L,R; 6 LL calc(LL x) { 7 if(x <= 7) return 0; 8 memset(cnt,0,sizeof cnt); 9 LL i = 2; 10 for(i = 2; i*i*i <= x; ++i) 11 cnt[i] = x/(i*i*i); 12 for(LL j = i - 1; j >= 2; --j) { 13 for(LL k = j + j; k < i; k += j) 14 cnt[j] -= cnt[k]; 15 } 16 LL ret = 0; 17 for(LL j = 2; j < i; ++j) 18 ret += cnt[j]; 19 return ret; 20 } 21 int main() { 22 int kase; 23 scanf("%d",&kase); 24 while(kase--) { 25 scanf("%lld%lld",&L,&R); 26 printf("%lld\n",R - L - calc(R - 1) + calc(L - 1)); 27 } 28 return 0; 29 }
HUST 1214 Cubic-free numbers II
原文：http://www.cnblogs.com/crackpotisback/p/4850503.html
