CF 264B(质因数分解)

D. Good Sequences
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

数列 n 有 a1, a2, ..., an 个数(严格递增),请从中任意删去一些数,使序列相邻2数都不互质。

问删后序列最长长度.

Input

第一行 n (1 ≤ n ≤ 105)
第二行序列 a1, a2, ..., an (1 ≤ ai ≤ 105ai < ai + 1).

Output

删后序列最长长度.

Sample test(s)
input
5
2 3 4 6 9
output
4
input
9
1 2 3 5 6 7 8 9 10
output
4
Note

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

错解:枚举开头即可。X

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
int n,a[MAXN];
bool b[MAXN]={0};
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);};
int main()
{
	scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int ans=0;
	for (int i=1;i<=n;i++)
	if (!b[i])
	{
		int len=1;
		b[i]=1;
		int head=i,tail=i+1;
		while (tail<=n)
		{
			if (gcd(a[tail],a[head])==1) tail++;
			else {b[head]=1;head=tail;tail++;len++;	}
		}
		ans=max(ans,len);
	}
	cout<<ans<<endl;

	return 0;
}

更正:

枚举开头不行,因为一个开头可能跟有多个序列(2,6,9)/(2,4)←选这个不忧

故枚举质因数,证明下:

若a和b不互质,则必存在质数k,使k|a&&k|b

故Dp如下:

 f[i,j]=max(f[i-1,k]+1) (k| a[i] 且j|a[i] ) 最大值len=f[i,j] 

//  f[i,j]  表示到第i个数为止,结尾是质数 j 的倍数的最大长度。

+上滚动数组后,得到如下的Dp方程

计算 len=max(f[k])+1 (k| a[i] )

更新:f[j]=max(f[j],len) (j|a[i]) 


注意质因数的分解中 先分解到√n,若此时未除尽,那一部分也要算进去(肯定是质数,否则必能再分)

eg:14=2*7(7=√49>√14)


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
int n,a[MAXN],f[MAXN]={0},st[MAXN],size;
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);};
void fac_prime(int x)
{
	size=0;
	for (int j=2;j*j<=x;j++)
	{
		if (x%j==0)
		{
			while (x%j==0) x/=j;
			st[++size]=j;
		}
	}
	if (x>1) st[++size]=x;
}
int main()
{
	scanf("%d",&n);
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if (a[i]==1) {ans=max(ans,1);continue;}
		fac_prime(a[i]);
		int len=0;
		if (st[1]==a[i]) {len=1;f[a[i]]=1;}
		else
			for (int j=1;j<=size;j++)
				len=max(len,f[st[j]]+1);

		for (int j=1;j<=size;j++) f[st[j]]=max(f[st[j]],len);
		ans=max(ans,len);
//		for (int j=1;j<=a[i];j++) cout<<f[j]<<' ';
//		cout<<endl;
	}
	cout<<ans<<endl;
	return 0;
}



Tyvj P2067(质因数分解)

P2067 - [NOIP2012P1]质因数分解

From luchangzhou    Normal (OI)
总时限:10s    内存限制:128MB    代码长度限制:64KB

背景 Background

NOIP2012

描述 Description

已知正整数n 是两个不同的质数的乘积,试求出较大的那个质数。

输入格式 InputFormat

 输入只有一行,包含一个正整数n 。

输出格式 OutputFormat

 输出只有一行,包含一个正整数p ,即较大的那个质数。 

样例输入 SampleInput [复制数据]

21

样例输出 SampleOutput [复制数据]

7

数据范围和注释 Hint

【数据范围】 
对于 60% 的数据 6 ≤ n ≤ 1000
对于 100%的数据 6 ≤ n ≤ 2*10^9

来源 Source

NOIP2012

O(√n)
注意要枚举1-√n而不是√n-n,数量级差很多。


#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
#define MAXAi (1000000000+10)
int n;
int main()
{
	cin>>n;
	for (int i=2;i<=n;i++)
		if (!(n%i))
		{
			cout<<n/i<<endl;return 0;
		}


}

Vijos 1490(判断整除的方法)

89/283(31%)   首页 站务 公告 | 题库/分类/原题 记录 比赛 团队 讨论 | U-S 搜索 换肤 正體 | 登出  
 
   
  公告 News >>   New! 关于noip2012模拟赛的公告 (2012-10-28
15:35:15)
   New! 关于Vijos10月份月赛的公告 (2012-10-26
14:44:09)
   关于第一期内测结束的公告 (2012-9-23 22:43:11)   关于Vijos9月份月赛的公告 (2012-9-20
17:31:48)
   Vijos月赛正式开通 (2012-9-16 11:35:36)
 
     

   
 
From dmh123x

小菜的数码验证 

 
     
   
  描述 Description  
  小菜最近在学数的数字数字特征,因此他打算编程来研究一下这个问题. 

他的问题很简单,输入一个数N(1000<N<10^31),判断是否能整除2, 3,4,8分别整除,同时判断它是否有可能(注意只是有可能) 

是完全平方数,依次输出1和0来表示能或不能. 
     
     
  输入格式 Input Format  
  一个自然数N(1000<N<10^31) 
     
     
  输出格式 Output Format  
  5个数,1或者0分别表示能和不能
     
     
  样例输入 Sample Input  
 
     
     
  样例输出 Sample Output  
 
     
     
  时间限制 Time Limitation  
  各个测试点1s 
     
   
 
Flag
Accepted
题号
P1490
数论 / 数值
通过
639人
提交
1270次
通过率
50%
难度
1
 
     
     
 
提交 讨论 题解 状态
 
     
     
 

 
     


 
 

这题坑爹的地方在于:可能是完全平方数就是一定满足……ToT

好了,具体参见目录,此题没必要高精。(尽管 10^31 不是 2^31……)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
char s[5000];
int find(int k)
{
	if (strlen(s)>=k) return s[strlen(s)-1-k+1]-48;
	return 0;
}
int main()
{
	scanf("%s",s);
	if (find(1)%2) cout<<"0"<<endl; else cout<<"1"<<endl;
	int tot=0; for (int i=1;i<=strlen(s);i++) tot+=find(i);
	if (tot%3) cout<<"0"<<endl; else cout<<"1"<<endl;
	if ((10*find(2)+find(1))%4) cout<<"0"<<endl; else cout<<"1"<<endl;
	if ((100*find(3)+10*find(2)+find(1))%8) cout<<"0"<<endl; else cout<<"1"<<endl;
	cout<<1<<endl;
	return 0;
}

附录:判定整除的一般性方法:

(1)1与0的特性: 

1是任何整数的约数,即对于任何整数a,总有1|a. 

0是任何非零整数的倍数,a≠0,a为整数,则a|0. 

(2)若一个整数的末位是0、2、4、6或8,则这个数能被2整除。 

(3)若一个整数的数字和能被3整除,则这个整数能被3整除。 

(4) 若一个整数的末尾两位数能被4整除,则这个数能被4整除。 

(5)若一个整数的末位是0或5,则这个数能被5整除。 

(6)若一个整数能被2和3整除,则这个数能被6整除。 

(7)若一个整数的个位数字截去,再从余下的数中,减去个位数的2倍,如果差是7的倍数,则原数能被7整除。如果差太大或心算不易看出是否7的倍 数,就需要继续上述「截尾、倍大、相减、验差」的过程,直到能清楚判断为止。例如,判断133是否7的倍数的过程如下:13-3×2=7,所以133是7 的倍数;又例如判断6139是否7的倍数的过程如下:613-9×2=595 , 59-5×2=49,所以6139是7的倍数,余类推。 

(8)若一个整数的未尾三位数能被8整除,则这个数能被8整除。 

(9)若一个整数的数字和能被9整除,则这个整数能被9整除。 

(10)若一个整数的末位是0,则这个数能被10整除。 

(11)若一个整数的奇位数字之和与偶位数字之和的差能被11整除,则这个数能被11整除。11的倍数检验法也可用上述检查7的「割尾法」处理!过程唯一不同的是:倍数不是2而是1! 

(12)若一个整数能被3和4整除,则这个数能被12整除。 

(13)若一个整数的个位数字截去,再从余下的数中,加上个位数的4倍,如果差是13的倍数,则原数能被13整除。如果差太大或心算不易看出是否13的倍数,就需要继续上述「截尾、倍大、相加、验差」的过程,直到能清楚判断为止。 

(14)若一个整数的个位数字截去,再从余下的数中,减去个位数的5倍,如果差是17的倍数,则原数能被17整除。如果差太大或心算不易看出是否17的倍数,就需要继续上述「截尾、倍大、相减、验差」的过程,直到能清楚判断为止。 

(15)若一个整数的个位数字截去,再从余下的数中,加上个位数的2倍,如果差是19的倍数,则原数能被19整除。如果差太大或心算不易看出是否19的倍数,就需要继续上述「截尾、倍大、相加、验差」的过程,直到能清楚判断为止。 

(16)若一个整数的末三位与3倍的前面的隔出数的差能被17整除,则这个数能被17整除。 

(17)若一个整数的末三位与7倍的前面的隔出数的差能被19整除,则这个数能被19整除。 

(18)若一个整数的末四位与前面5倍的隔出数的差能被23(或29)整除,则这个数能被23整除