首页 > 其他分享 >筛法思想的题目

筛法思想的题目

时间:2024-02-08 19:11:41浏览次数:27  
标签:题目 筛法 思想 int rep long 数有 define

image
这道题目比较经典,或者说这种思想比较经典。
这种筛法的思想。
我们正着想对于每一个\(n、 n-1、n-2、...、2、1\)都分解一遍质因数显然是来不及的时间复杂度达到\(O(n \sqrt{n})\)
我们考虑对于每一个1e6以内的质因数的个数
image
跑了一下程序是\(78498\)个

素数定理告诉我们不超过x的素数近似有\(\frac{x}{lnx}\)个

对于每一个质因子我们看一下那些数有一个这个质因子,那些数有两个,那些数有3个这个每次是平方的增长很快
时间复杂度:\(O(\frac{n}{logx} * logn)\)近似\(O(n)\)

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

const int N=1e6+10,mod=1e9+7;
int vis[N];
vector<int>p;
void solve()
{
	int n;cin>>n;
	auto get=[&](int x){
		rep(i,2,x){
			if(!vis[i])	p.pb(i);
			for(int j=0;p[j]*i<=x;++j){
				vis[i*p[j]]=1;
				if(i%p[j]==0)	break;
			}
		}
	};
	get(1e6);
	cout<<p.size()<<endl;
	int res=0;
	vector<int>ans(n+1);
	rep(i,0,p.size()-1){
		for(int j=p[i];j<=n;j*=p[i]){
			ans[i]+=n/j;
			res+=n/j;
		}
	}
	rep(i,0,p.size()-1){
		cout<<p[i]<<' '<<ans[i]<<endl;
	}
	return;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

标签:题目,筛法,思想,int,rep,long,数有,define
From: https://www.cnblogs.com/cxy8/p/18012012

相关文章

  • 质数基础筛法
    目录埃氏筛线性筛埃氏筛埃氏筛是一种筛素数的方法,埃氏筛的思想很重要,主要是时间复杂度朴素的埃氏筛的时间复杂度是\(O(nlogn)\)这个复杂度是调和级数vector<int>p;intvis[N];voidsolve(){ rep(i,2,n){ if(!vis[i]) p.pb(i); for(intj=i+i;j<=n;j+=i) vis[j]=1; ......
  • (C语言)代码学习||2024.2.6||题目是codewars上的【 IP Validation】
    C语言#sscanf#代码学习#codewars题目链接:IPValidation|Codewars代码如下:#include<stdio.h>intis_valid_ip(constchar*addr){unsignedn[4],i,nc;//Mustbe4integersseparatedbydots:if(sscanf(addr,"%d.%d.%d.%d%n",&n[0],&n......
  • (python)代码学习||2024.2.4||题目是codewars的【 All Balanced Parentheses】
    题目链接:https://www.codewars.com/kata/5426d7a2c2c7784365000783/pythondefbalanced_parens(n):'''Toconstructallthepossiblestringswithnpairsofbalancedparenthesesthisfunctionmakesuseofastackofitemswiththefoll......
  • 复杂系统 | 20240116 · 考试题目回忆版
    相关链接:RL基础|ValueIteration的收敛性证明RL基础|PolicyIteration的收敛性证明复杂系统|考前知识点总结(不完全)“嵌套分区法,是一种良策;将海洋分成块,每块都探测。”概述:基于事件的优化方法/事件驱动优化/Event-BasedOptimization/EBO十个判断题,感觉......
  • 使用分形思想,通过图灵完备的机器赛跑关卡,并获得小机快跑成就
    本文作者:Wyu-Cnk前言最近在玩图灵完备(TuringComplete)一路过关斩将,来到机器赛跑(RobotRacing)这一关的时候,一看地图对于选修过分形几何的我来说,这不就是熟悉的希尔伯特曲线嘛!老朋友了!于是我复活已经死去的和分形几何有关的记忆,用分形的思想初步实现了对应的汇编......
  • 经典数据结构题目-图
    图200.岛屿数量思路遍历二维数组,遇到等于1的进行计算。同时修改同岛的位置为0,避免重复计算遍历同岛的位置,可以采用dfs深度优先搜索代码char[][]g;publicintnumIslands(char[][]grid){intsum=0;g=grid;for(inti=0;......
  • (python)做题记录||2024.2.4||题目是codewars的【 All Balanced Parentheses】
    题目链接:https://www.codewars.com/kata/5426d7a2c2c7784365000783/python我的解决方案:defbalanced_parens(n):#Yourcodehere!used_l=[Falseforiinrange(n)]used_r=[Falseforiinrange(n)]answers=[]defprocess(answer):iflen(a......
  • 根据筛法规则对整数分类,建立树状结构
    筛法目前一般用来找整数序列中的素数,不是素数的元素被丢掉了。如果仅把筛法当成一种分类规则,把筛掉的元素和留下的元素算作不同的分类,并用每一类中的最小元素递归地执行筛法,那么能把所有正整数保留下来,并建立一个树状结构。例如,初始集合是正整数集,根据模最小元素p是否为0,可把所有......
  • (python)代码学习||2024.2.3||题目是codewars上的【Validate Sudoku with size `NxN`
    题目的要求是写一个Sudoku类,类中要有一个实例函数判断传给对象的二维数组是否符合数独规则题目链接:https://www.codewars.com/kata/540afbe2dc9f615d5e000425/python下面是写完题后看到的别人的解决方法fromitertoolsimportchainclassSudoku(object):def__init__......
  • 基础算法(八)前缀和模板---以前缀和题目为例
    题目如下输入一个长度为 n的整数序列。接下来再输入 m个询问,每个询问输入一对 l,r。对于每个询问,输出原序列中从第 l 个数到第 r个数的和。输入格式第一行包含两个整数 n 和 m。第二行包含 n 个整数,表示整数数列。接下来 m 行,每行包含两个整数 l 和 r,......