首页 > Forsaken喜欢数论

zzugzx

发表于 2020-06-22 15:22:29

题目链接题意：题解： AC代码 #include<bits/stdc++.h> using namespace std; const int N = 3e7 + 10; int prime[N]; int miniFactor[N]; int primepos; void 展开全文

与人无语

发表于 2020-07-11 15:31:22

把筛法改一改就行了最先到的就是最小质素因子 #include <bits/stdc++.h> #define ll long long using namespace std; int const N=3e7+5; ll p[N],ans,n; int main() { ci 展开全文

BeauWill

发表于 2026-03-28 02:21:08

Modern Cpp欧拉筛是可以用最小质因子筛的，jiangly老师的欧拉筛模板就是如此。然后累加1到n的最小质因子即可。 #include <iostream> #include <vector> #include <numeric> std::vector& 展开全文

憨憨的竹林

发表于 2026-03-28 00:10:59

其实就是欧拉筛质因数的时候顺道拿数组记录一下每个数的最小质因子就好了，然后累加一下就好了没学过欧拉筛的先学完再来做感觉会好很多上代码：（详细内容见注释） #include <bits/stdc++.h> using namespace std; #define endl '\n' #de 展开全文

sunsetcolors

发表于 2020-06-22 15:51:10

Forsaken喜欢数论题目地址： https://ac.nowcoder.com/acm/problem/53079 基本思路：其实就是一个素数筛，我们想一下在埃氏筛法的过程中，我们是从小到大的对于每个质数，将它的倍数都筛掉，那么这个质数其实就是这些被筛掉的非质数的质因子，并且由于我们展开全文

Canan

发表于 2020-06-22 15:57:48

https://ac.nowcoder.com/acm/problem/53079题意：给定一数n，求1~n每个数的最小质因数的和。分析：可以用欧拉线性筛素数法，每个数仅使用其最小素因数筛去，开始先打个表，后面直接统计答案就行了。代码： #include<stdio.h> #incl 展开全文

AliLexiWalker

发表于 2026-03-28 00:05:04

这题其实就是把每个数的最小质因子都快速找出来再累加，1 的最小质因子按题意算 0，所以不用加。直接用线性筛：一边筛素数，一边给每个合数打上“第一个质因子”标签，这样每个数都只会被处理常数次，整体是 O(n)。最后把 2 到 n 的最小质因子加起来就是答案。 void solve(){ i 展开全文

dilingtian

发表于 2022-11-03 00:13:36

欧拉筛题解欧拉筛欧拉筛法可以在线性的时间复杂度里筛出N以内的所有质数 vector<long long> oula(long long n) { vector<long long> prime; vector<bool> vis(n + 1 展开全文

olone

发表于 2026-03-28 09:42:05

import java.util.*; public class Main{ static final int N = 30000005; public static void main(String[] args){ Scanner in = new Scanne 展开全文

olone

发表于 2026-03-28 09:47:19

import java.util.*; public class Main{ static final int N = 30000005; public static void main(String[] args){ Scanner in = new Scanne 展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛