题目大意:
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.
解题思路:
所有的real number即是大于4的不是偶数平方的偶数或者奇数平方的奇数。
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#define LL long long using namespace std;LL solve(LL n){if(n <= 4) return 0;LL res = (n – 4) / 2;LL t = sqrt(n);if(t & 1) res ++;return res;}int main(){LL l, r;int T;scanf("%d", &T);while(T–){cin>>l>>r;cout<< solve(r) – solve(l-1)<<endl;}return 0;}
,只要相信,期待就会成真