题解 | #质数#

真是个数学问题。。。。

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);
    }
}