题目链接:https://ac.nowcoder.com/acm/problem/211962

到主站看:https://blog.csdn.net/weixin_43346722/article/details/109631931

题目

我们定义 之外的所有因子
外所有因子的
询问从

输入

输入两个正整数

输出

输出一个正整数表示答案

样例输入

5 7

样例输出

13

数据范围

对于 的数据,
对于 的数据,
对于 的数据,

思路

这道题是一道数学题。

题目的 函数要的是一个数所有除了 的因子的

我们大概想想就会发现,如果这一个数分解质因数可以分解出不止一种质数,那的出来的 函数值就是
(因为这个数至少会有这两个质数为因子,而两个质数的 又是一,那的出来就只能是 了)

那我们就先素数筛选法找出 以内的质数,然后对于每一个质数,就枚举多少个这个质数乘在一起,对于每一个数,它对答案的贡献就是那个质数。
最后还没有对答案产生贡献的数,就是由不止一个质数乘起来得到的数,对答案的贡献就是

的话就是对答案贡献 ,所以可以算在由不止一个质数乘起来得到的数里面)

代码

#include<cstdio>

using namespace std;

long long a, b, ans, susu[10000024], tot;
bool yes[10000024];

int main() {
    scanf("%lld%lld",&a,&b);   

    for(long long i = 2; i <= b; i++) {
        if(!yes[i]) susu[tot++] = i;
        for(long long j = 0; j < tot && i * susu[j] <= b; j++)
            yes[i * susu[j]] = 1;
    }

    ans = b - a + 1;//先假设全部贡献都是 1

    for(long long i = 0; i < tot; i++)
        for(long long j = susu[i]; j <= b; j *= susu[i])
            if(a <= j) ans += susu[i] - 1;//是质数的贡献,就让贡献加上质数减去之前加上的 1

    printf("%lld", ans);

    return 0;
}