首页 > 试题广场 >

质数

[编程题]质数

热度指数：793 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个质数p，和两个区间 $\left [ a,b \right ]$ ， $\left [ c,d \right ]$ ，分别在两个区间中取一个数x，y。求有多少对 $\left ( x,y\right )$ 使得 $x \ast y$ 是p的倍数。给定你两个区间，求从区间中取出数相乘是p的倍数的个数。

示例1

输入

3,7,4,6,3

输出

说明

(3,4),(3,5),(3,6),(4,6),(5,6),(6,6),(7,6),(6,4),(6,5)一共有9个

备注:

，数据保证p为质数

算法知识视频讲解

牛客37697243号

为什么测试永远是超时😅

    public long numbers (int a, int b, int c, int d, int p) {
        long countLeft = 0;
        for (int i = a; i <= b; i++) {
            if (i % p == 0) {
                countLeft ++;
            }
        }

        long countRight = 0;
        for (int i = c; i <= d; i++) {
            if (i % p == 0) {
                countRight ++;
            }
        }
        return countLeft * (d - c + 1) + countRight * (b - a + 1) - countLeft * countRight;
    }

发表于 2021-02-03 15:31:44 回复(1)

Java

LibraXiong

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
long sum1=count(a,b,p);
long sum2=count(c,d,p);
return sum1*(d-c+1)+sum2*(b-a+1)-sum2*sum1;

}
public long count(int begin,int end,int p){
return end/p-(long)Math.ceil(1.0*begin/p)+1;
}
}

发表于 2022-01-16 00:31:26 回复(0)

牛客381719688号

为了不超时用纯数学方法做了

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
        long count1 = a%p!=0? b/p-a/p:b/p-a/p+1;
        long count2 = c%p!=0? d/p-c/p:d/p-c/p+1;
        long res=count1*(d-c+1)+count2*(b-a+1)-count1*count2;
        return res;
    }
}

发表于 2021-05-20 15:35:35 回复(0)