2015年ALPC暑期代码能力练习I D Upgrading Array_d. upgrading array-程序员宅基地

技术标签: 2015暑期训练  

题目链接:http://codeforces.com/problemset/problem/402/D

又WR了N次,卡了2天,最后问别人才直到错误在哪里。在初始化素数数组时是i*i<MAX_INT,如果输入的数是一个素数且>素数数组中最大的素数,那么这个数没有被统计。大神们一看就知道错误在哪里,可怜我卡了这么久。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<map>
#include<set>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
/*********************************************************************/
const int MAX_NUM = 5000+500;
const int MAX_INT = 1000000000+10;
int a[MAX_NUM];
int allGcd[MAX_NUM];
vector<int> badPrime;
vector<int> allPrime;

void swap (int& a,int& b){a^=b;b^=a;a^=b;}
int min_2 (int a,int b){return a<b?a:b;}
int max_2 (int a,int b){return a>b?a:b;}
int gcd (int a,int b){return b==0?a:gcd(b,a%b);}

void InitGoodPrime ()
{
  allPrime.push_back (2);
  int sign=1;
  for (int i=3;i*i<MAX_INT;++i){
	sign=1;
	for (int j=0;j<allPrime.size ();++j)
	  if (i%allPrime[j]==0){sign=0;break;} 
	if (sign)
	  allPrime.push_back (i);
  }
}
int JudgeGcd (int x)
{
  int sum=0;
  for (int i = 0; i<badPrime.size (); i++){//统计坏素数的个数
	while (x%badPrime[i]==0) {
	  x/=badPrime[i];
	  --sum;
	}
  }
  for (int i = 0; i<allPrime.size () && allPrime[i]<=x; i++){//统计好素数的个数,坏素数已经被除尽
	while (x%allPrime[i]==0) {
	  x/=allPrime[i];
	  ++sum;
	}
  }
  if (x!=1)//素数只统计到sqrt(MAX),如果x!=1就是大于allPrime中的最大素数,而且x一定是素数
	++sum;
  return sum;
}
/*********************************************************************/
int main()
{
  int n,m;
  allPrime.clear ();
  InitGoodPrime ();
  while (scanf ("%d %d",&n,&m)!=EOF)
  {
	for (int i=0;i<n;i++)
	  scanf ("%d",&a[i]); 
	badPrime.clear ();
	int bad;
	for (int i=0;i<m;i++){
	  scanf ("%d",&bad);
	  badPrime.push_back(bad);
	}
	allGcd[0]=a[0];
	for (int i=1;i<n;i++)
	  allGcd[i]=gcd (allGcd[i-1],a[i]);
	int div[MAX_NUM];
	div[n]=1;
	for (int i=n-1;i>=0;i--){
	  if (JudgeGcd (allGcd[i]/div[i+1])<0)//考虑后面已经除了。如果再除的数,坏素数多,就除以gcd
		div[i]=allGcd[i];
	  else
		div[i]=div[i+1];//否则就除以后面那个数的除数
	  a[i]/=div[i];
	}
	int source=0; 
	for (int i=0;i<n;i++)
	  source+=JudgeGcd (a[i]);
	printf ("%d\n",source);
  }
  return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u011575516/article/details/46976349

智能推荐

Axure设置Tab切换_axure7.0 tab切换‘’-程序员宅基地

文章浏览阅读792次。一、制作Tab页面1、 拖入一个矩形去掉3个边,只留下下单边,如果你用的我的《快速原型组件库》,可以直接拖入“下单边矩形”,设置一下尺寸为100×40(尺寸这种东西,可以按自己需求来,下同),起个名字Tab1(给原件起名字这个习惯一定要养成,方便自己,也方便别人)2、 交互样式设置设置了鼠标悬停样式及选定样式,此处可根据你的需求自行调整样式3、设置选项组名称选项组的功能,一般用在表单的单选框上,相同的选项组,可以联动单选,此处,我们可以将普通元件编组,同样让其具有.._axure7.0 tab切换‘’

php redis统计在线人数,每天活跃度_用 swoole redis 分别统计每天,每小时,每分钟的在线人数-程序员宅基地

文章浏览阅读2.3k次。1.项目中使用的是每5分钟向接口发包,激活用户。 //用户在线激活 public function user_activate(){ $code = $this-&gt;param['code']; $redis = new \myredis\Datasource(); $myredis = $redis::getRedis('insta..._用 swoole redis 分别统计每天,每小时,每分钟的在线人数

软件质量保证与软件测试 第三周(决策表+黑盒测试总结)+第四周(路径测试(白盒测试的一种)+各种覆盖判定的计算)_弱健壮等价类测试用例的个数怎么算-程序员宅基地

文章浏览阅读533次。从一个例子来理解各种覆盖指标:(重点重点重点!!!语句覆盖就是点覆盖判定覆盖就是边覆盖条件覆盖就是每个条件正反至少有一次判断条件覆盖就是:每个判断分支至少走一次、且每个条件至少走一次条件组合覆盖:每一个条件的正反都进行笛卡尔积。_弱健壮等价类测试用例的个数怎么算

BigDecimal舍入模式ROUND_HALF_UP和ROUND_HALF_DOWN区别-程序员宅基地

文章浏览阅读3.9w次,点赞10次,收藏11次。ROUND_HALF_UP和ROUND_HALF_DOWN都是向最接近的数字舍入,区别在于当与相邻的数字距离相等时两者的舍入模式不同ROUND_HALF_UP是我们常用的四舍五入,即舍入部分大于等于0.5时进位,否则丢弃舍入部分ROUND_HALF_UP通俗地说是五舍六入,即舍入部分大于0.5时进位,否则丢弃舍入部分例如:当num=1.5,保留0位,ROUND_HALF_UP=2 , ...

PHP正则表达式验证手机号、邮箱、身份证号码、姓名等_php身份证正则表达式-程序员宅基地

文章浏览阅读1.4w次,点赞3次,收藏18次。在PHP编写的程序中,为了保证代码本身的流程安全,少不了对数据流进行一些效验的工作。而PHP给我提供了正则表达式验证函数,我们可以很方便的通过正则表达式的验证函数,来检查数据流是否符合标准。今天我们就列出一些常用的正则表达式,就当做一个记录吧。PHP正则表达式匹配函数preg_match()preg_match() 函数用于进行正则表达式匹配,成功返回 1 ,否则返回 0 。语法:int preg_match( string pattern, string subject [, arr_php身份证正则表达式

物联网入门:构建你的第一个IoT系统_从零开始学iot-程序员宅基地

文章浏览阅读884次。物联网(Internet of Things,缩写为IoT)是一种信息技术产业,它利用现代电子技术、通信技术、计算技术、信息技术、生物技术等综合实现的技术手段,将各种物理设备通过互联网、无线传输数据、网络连接,并使得这些设备不断地产生和处理数据,以提高它们的功能、效率和智能性。换句话说,物联网就是利用网络技术、信息技术和生物技术,将互联网技术、RFID、ZigBee、蓝牙、LoRa、WiFi、4G等各种通讯方式应用到现实世界中,实现真正意义上的物联网。那么,如何开发一个真正的物联网系统呢?_从零开始学iot

随便推点

低通、高通数字滤波器——C语言单片机实现_基于单片机的数字带通滤波器-程序员宅基地

文章浏览阅读1.5w次,点赞66次,收藏266次。低通、高通数字滤波器——C语言单片机实现一阶滤波器高阶滤波器博主刚好进入研二,研究的方向刚好涉及到数字滤波这一块,因此花了一周时间钻研了下数字滤波的实现。由于本科是电气专业,所以没有数字信号处理相关知识,在一开始看数字信号处理相关理论的时候就显得比较力不从心,尤其是难懂的数学公式。相比看到这里的读者多多少少也有类似的体会。好在功夫不负有心人,本博主从繁琐的公式中,加上其他博主的博客讲解,领悟了如何使用C代码实现几种经典数字滤波器,可以使其在VS或者单片机上运行而不受限于在matlab上跑仿真。当然在_基于单片机的数字带通滤波器

基础的总结_int f(int i) { if (i==1||i==2) return 1; else retu-程序员宅基地

文章浏览阅读75次。基础语法注释和标识符单行注释//多行注释/**/文本注释/** */类型八大基础类型float 后面加3.14f,long后面加123123l剩下的都为引用数据类型string 不是关键字拓展0零开头为八进制0b为二进制0x为十六进制如果使用大数字可以用int 1_0000_0000//里面的下划线不会被记如果是银行要记录精度的数字用BigDecimal数据类型如果a=10,b=2a=10,b=20;a+b+"_int f(int i) { if (i==1||i==2) return 1; else return f(i-1)+f(i-2); } int

window时不时蓝牙无法使用解决方案_window ble 连接总失败-程序员宅基地

文章浏览阅读354次。遇到过同样的问题,解决方法是右击开始,进入设备管理器,找到未知USB设备,先右击禁用,再右击启用,行了。_window ble 连接总失败

C# 文件操作大全-程序员宅基地

文章浏览阅读226次。1.创建文件夹//using System.IO;Directory.CreateDirectory(%%1);2.创建文件//using System.IO;File.Create(%%1);3.删除文件//using System.IO;File.Delete(%%1);4.删除文件夹//using System.IO;Directory.Delete(%%1);5.删除一个目..._c#如何文件流转为0x1

Codeforces 1354 C1. Simple Polygon Embedding_codeforces1354c-程序员宅基地

文章浏览阅读10w+次。题意:给定 nnn,求能包围正 2∗n2*n2∗n 边形的正方形的最小面积。nnn 为偶数时,正多边形必有四条边分别和正方形的四条边重合,可以推出公式:ans=2∗(12∗1tan(360。/n∗2/2))ans=2*(\frac{\frac{1}{2}*1}{tan(360^。/n∗2/2)})ans=2∗(tan(360。/n∗2/2)21​∗1​)AC代码;const double PI = 3.1415926535898;int n, m;int main(){ int t; ._codeforces1354c

《数据结构》实验四----链栈的基础操作-程序员宅基地

文章浏览阅读227次。/*LinkStack.c*/#include <stdio.h>#include <stdlib.h>#include "LinkStack.h"#include <windows.h>void InitStack(LinkStack* top)//栈链初始化{ if((*top=(LinkStack)malloc(sizeof(LStackNode)))==NULL) exit(0); (*top)->next=NUL

推荐文章

热门文章

相关标签