POJ 1619 EKG Sequence（EKG数列 ，数据处理技巧）
发布时间：2020-12-14 03:05:10 所属栏目：大数据 来源：网络整理
导读：分析： 此题的结构是按从前往后用位置挑选合适的数字。每一次，枚举前一位置 数字 素因子，用素因子寻找用同样拥有该素因子且未进队的最小整数(公因子可以分解成素因子)， 伪代码： ? ? ? ? ans=INF； ? ? ? ? 枚举前一位置素因子 ? ? ? ? { ? ? ? ? ? ? 寻
|
分析：此题的结构是按从前往后用位置挑选合适的数字。每一次，枚举前一位置数字素因子，用素因子寻找用同样拥有该素因子且未进队的最小整数(公因子可以分解成素因子)，
伪代码：
? ? ? ? ans=INF；
? ? ? ? 枚举前一位置素因子 ? ? ? ? { ? ? ? ? ? ? 寻找用同样拥有该素因子且未进队的最小整数； ? ? ? ? ? ? 更新ans=min（最小整数，ans） ? ? ? ? } 现在位置=ans; 代码： <span style="font-family:SimSun;font-style: normal;">#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN=1000005;
int rec[MAXN],nex[MAXN],b[MAXN];
void make_table()
{
int i,j;
rec[1]=1;
rec[2]=2;
for(i=1;i<MAXN;i++)//拥有因子为i且未进队的最小整数（实际上后面代码只用了其中下标为素因子的部分）
nex[i]=i;
nex[2]=4;
for(i=2;i<MAXN;i++)//b[]存储每个数字的最小素因子，
if(b[i]==0)
{
for(j=1;i*j<MAXN;j++)
if(b[i*j]==0)b[i*j]=i;
}
int cur=2;
for(i=2;i<MAXN;i++)
{
int k=cur;
cur=MAXN;
for(int p=b[k];p!=1;)
{
while(rec[nex[p]]&&nex[p]+p<MAXN)//更新
nex[p]+=p;
cur=min(cur,nex[p]);
while(k%p==0)k=k/p;//查找下一个素因子
}
rec[cur]=i+1;//找到该位置的数字，并在以数字为索引的数组里存进位置标号
}
}
int main()
{
int n;
make_table();
while(~scanf("%d",&n)&n)
{
printf("The number %d appears in location %d.n",n,rec[n]);
}
return 0;
}</span>
部分参考于：POJ 1619 EKG Sequence （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |