真是个数学问题。。。。
O(log2n)过不了,只能常数。。。。
class Solution { public: /** * 返回两个区间内各取一个值相乘是p的倍数的个数 * @param a int整型 第一个区间的左边界 * @param b int整型 第一个区间的右边界 * @param c int整型 第二个区间的左边界 * @param d int整型 第二个区间的右边界 * @param p int整型 质数 * @return long长整型 */ long long numbers(int a, int b, int c, int d, int p) { // write code here long long cnt0=0,cnt1=0;//cnt0为第一个区间内质数个数 cnt0=b/p-(a-1)/p; cnt1=d/p-(c-1)/p; cout<<cnt0<<" "<<cnt1<<endl; return cnt0*(d-c+1)+cnt1*(b-a+1)-cnt0*cnt1; } };
JAVA:
import java.util.*; public class Solution { /** * 返回两个区间内各取一个值相乘是p的倍数的个数 * @param a int整型 第一个区间的左边界 * @param b int整型 第一个区间的右边界 * @param c int整型 第二个区间的左边界 * @param d int整型 第二个区间的右边界 * @param p int整型 质数 * @return long长整型 */ public long numbers (int a, int b, int c, int d, int p) { // write code here return (long)(b/p-(a-1)/p)*(d-c+1)+(long)(d/p-(c-1)/p)*(b-a+1)-(long)(b/p-(a-1)/p)*(d/p-(c-1)/p); } }