【问题描述】

$hh$是一名新人魔法师，在魔法考试中遇到难题，现求助于你。

有一个长度为$n$的魔法数字序列，你需要从中选出一些魔法数字来，保持这些魔法数字在原来序列的相对位置组成一个新的魔法数字序列，使得相邻的两个魔法数字不互质。输出新魔法数字序列最长长度。

两个魔法数字不互质即它们的最大公约数应该大于$1$

【输入格式】

第一行，一个整数$n$，表示原序列的长度。

第二行，$n$个数，表示序列中的元素。

【输出格式】

输出新序列的最长长度，数据保证答案至少为$2$。

【输入样例1】

$7$

$2$ $3$ $4$ $5$ $6$ $7$ $8$

【输出样例1】

$4$

样例说明

$2$ $4$ $6$ $8$ 即为符合条件的最长新序列

【数据范围与提示】

​ 对于20%的数据，所有输入数据的范围$[1,20]$;

​ 对于40%的数据，所有输入数据的范围$[1,10^3]$;

​ 对于70%的数据，所有输入数据的范围$[1,10^5]$;

​ 对于100%的数据，所有输入数据的范围$[1,10^6]$;

$AC$

#include <iostream>
using namespace std;
int p[1000005][15],dp[1000005],a,n,m2=-2,s;
int Dp(int x){
	int m1=-1;
	for(int j=1;j<=p[x][0];j++){
		dp[p[x][j]]++;
		m1=max(m1,dp[p[x][j]]);
	}
	for(int j=1;j<=p[x][0];j++){
		dp[p[x][j]]=m1;
	}
	return m1;
}
int main(){
    for(int i=2;i<=1e6;i++){
		if(p[i][0]==0){
			for(int j=i;j<=1e6;j+=i){
				p[j][++p[j][0]]=i;
			}
		}
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
        m2=max(Dp(a),m2);
	}
	cout<<m2;
    return 0;
}

$WA$

#include <iostream>
using namespace std;
int p[1000005][15],dp[1000005],a[1000005],n,m2=-2,s;
int Dp(int x){
	int m1=-1;
	for(int j=1;j<=p[x][0];j++){
		dp[p[x][j]]++;
		m1=max(m1,dp[p[x][j]]);
	}
	for(int j=1;j<=p[x][0];j++){
		dp[p[x][j]]=m1;
	}
	return m1;
}
int main(){
    for(int i=2;i<=1e6;i++){
		if(p[i][0]==0){
			for(int j=i;j<=1e6;j+=i){
				p[j][++p[j][0]]=i;
			}
		}
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		m2=max(Dp(a[i]),m2);
	}
	cout<<m2;
    return 0;
}

过不了的数据之一

输入

99998
38009 4135 53688 99563 63593 7703 9582 58240 3848 35818 53920 73441 35544 8028 85769 87560 30921 32444 58133 18915 58299 16175 4629 62791 51347 9011 11728 42530 68036 47527 75296 8751 43796 57227 89587 95769 21199 50762 10891 72641 86981 92538 86593 81707 64369 2441 25782 25700 46797 43763 90769 35678 88735 91470 12650 67590 73382 35484 26216 36762 5451 51722 75413 35125 73172 36137 25325 93525 64610 92549 88145 55637 92344 73730 89816 81650 98216 49079 45096 57236 11742 63593 53546 31160 85220 52399 79618 29438 49482 29900 21936 96259 2368 25016 1559 50378 24188 24986 22315 9935 30944 68708 43371 86085 69978 17300 22962 43826 4184 41571 69197 83876 78817 17867 61283 46379 49502 18155 4263 62584 29054 2094 59853 68379 79524 67610 40347 95375 28874 81755 14138 20922 38862 6508 80453 93792 77499 50469 79078 64658 67887 83700 69483 29147 42187 81353 24983 19808 54398 31216 2416 47906 12225 20770 12506 18742 33056 38566 7823 48274 16592 30605 64313 42735 54032 68612 46928 37901 43658 70139 71957 2340 76976 33443 68581 75281 36001 10212 10141 39754 53593 17005 5553 2921 82946 26465 99020 57764 98800 4875 92996 76333 61608 10065 43278 60592 93093 47821 83377 90076 91555 34261 49403 38981 30281 44256 40883 34658 74319 58678 95687 65777 88304 67317 20452 95918 34804 93071 86087 37097 50327 55886 31891 18642 25235 68228 79956 85370 23760 95416 57833 99577 24979 37505 47699 9558 59985 88697 57799 81506 21135 45161 30998 23384 24906 96476 77747 32046 61234 49025 99883 54977 61646 52571 8723 66341 57372 32999 10093 74210 73515 2222 18549 51414 90110 96239 44351 65460 50663 21811 58520 20052 99687 13049 19136 75500 74330 61946 65494 61310 52515 77006 89144 93003 59446 30581 63352 66543 90335 38546 985 77146 36338 66920 2999 66341 1395 55187 33302 7589 36405 72425 16815 43339 75151 20993 22280 57018 87249 57188 97308 84125 10909 46800 38952 96131 47910 34640 45578 79952 33668 27150 85610 30515 86824 70382 85383 52103 49890 22538 17770 82994 71507 13971 19250 35714 40664 66750 17078 25205 13534 49025 77999 48348 3647 83992 2832 86798 53727 38138 97274 48607 43948 14967 44054 75305 9014 41986 28739 48487 55694 12569 92374 69824 82628 60053 95983 85882 33036 20009 80834 52733 28941 1022 46934 73850 58247 73574 90858 88152 78111 74832 92571 95748 6740 30494 80273 71297 3278 16041 58385 784 75577 12620 5197 93485 19739 47936 53296 24575 65257 98246 58322 29511 3647 56889 71252 2180 14549 16546 62357 18343 3296 54724 35888 14132 2446 91411 77402 61548 86537 28568 90806 79488 95019 8195 37874 4271 92727 31358 17434 70485 85823 75449 53777 62021 2220 58035 88034 80650 51832 34594 43216 36452 79186 71582 66010 81654 95030 24491 39762 49016 34859 40971 27338 73493 63602 586 98168 61183 81900 83321 23246 7777 30732 86024 54206 36341 41025 14285 77716 59913 40942 29320 86813 53906 57598 64100 1120 88709 30998 67859 48865 36905 69661 65210 23886 67313 41780 51663 56048 35667 61463 81491 10500 13223 79571 15029 20210 96527 4562 38352 36057 24320 6463 36165 28214 58835 92954 80030 9381 55817 11321 31820 15950 92012 11060 46404 62299 20810 86435 61300 33495 60572 54335 18362 97097 25721 19324 47477 53146 67576 89633 92416 22217 44006 34229 88574 94907 47342 98161 24 86690 61697 24299 73006 3135 61464 92786 91994 97259 62597 78632 48980 81515 37307 88836 74360 1742 16635 96530 51146 57956 97264 84369 61561 81343 57145 51113 37508 69469 87728 50267 13475 80240 69488 22804 32112 93913 47685 44487 78642 78950 50311 85202 54867 75332 38105 74070 5815 77744 42223 33699 3036 82222 6827 42458 16535 42554 96038 78297 24371 17704 85251 13922 81227 80320 78067 20747 10688 99827 93255 57365 94143 8327 56628 60235 91499 67507 97720 16379 99296 27947 69813 49325 24634 53236 90218 85140 10729 51501 83564 6196 82053 80308 90149 14828 54758 19075 57263 60656 56017 76655 64692 40759 99866 74873 32873 90722 76856 1751 65503 4588 83087 40547 50557 37957 56623 65183 8702 613 78176 896 95932 43589 59856 91526 75105 98984 7767 6300 22258 1667 54335 3639 23494 34154 58484 10260 20702 91827 49736 27718 83081 98156 48318 87365 11189 6857 2304 88838 60779 7580 15206 64829 38457 9816 42789 50252 38621 20261 9830 51167 50819 22231 49880 60842 99758 78996 81694 85283 93039 77528 9891 41219 10066 12470 3558 57242 83242 45371 27402 46742 82397 8699 6851 15941 4509 41120 49682 25838 90806 22882 11453 6948 59237 8548 28636 83063 67024 1248 32321 54560 66965 42983 86546 82784 64466 83389 17130 4172 10217 88226 24418 67691 23630 70822 59027 94835 41044 49104 40493 70784 23443 66053 93546 15569 30504 1847 32965 22839 77 58541 76163 74009 19494 77576 69287 19809 72782 25998 12548 21834 65228 59432 8483 17903 47243 89377 66974 35693 26415 23787 14083 59974 26029 83093 39835 90027 15693 61500 86759 42776 98830 92180 23186 52010 80984 52742 14317 57545 94304 94097 53532 53694 38492 72156 3797 19808 21145 28808 59637 42595 77114 98834 3522 59570 91856 99494 28685 15542 21835 64271 57719 70440 46440 27941 96819 31752 27851 31707 49381 24356 44535 45488 86793 79711 14687 69201 21841 47618 96248 4538 49847 79061 31898 59411 93458 55542 52310 68713 33335 87934 77438 71441 17866 23123 213 41816 30067 68726 81166 71948 6011 74 63828 65854 9258 16526 47815 41204 3443 32015 80083 38135 7961 43490 86864 23448 21652 18216 2504 34104 23495 81552 19495 37326 58981 63162 41648 10571 3068 68952 27497 23226 59870 63057 89579 71178 11389 68373 68918 58584 44985 18465 79570 17351 50889 85543 57493 31281 47920 74417 2485 7133 14969 13706 52338 16274 78473 572 2599 65880 14414 31625 81168 58232 88318 2942 26111 64920 25532 32429 50657 87332 7005 91662 97439 94286 15163 73256 95110 5993 16570 33968 47810 28325 47738 19667 49817 90137 36201 72258 49029 48987 68231 66615 77366 38870 49484 60416 677 8368 78761 99564 13514 41840 54480 69179 88669 20293 80213 80624 50678 10967 31021 71630 82075 34955 30845 34454 1592 49322 39194 24335 52751 93126 72667 72208 79905 56759 8981 18745 38450 28415 49096 73803 7981 34405 65975 42518 29774 75381 36461 90373 18803 9106 22902 83478 6722 83603 18263 69496 47514 21001 89124 92702 10864 8140 5506 98031 21505 14360 14564 22758 35948 74178 24013 68123 9407 1707 60653 53645 97463 99576 30038 26632 95861 58693 86285 86664 6139 39944 40763 9042 52220 72625 87210 9870 34211 5010 30656 54185 44309 54938 63821 9368 34064 63250 10264 64550 80696 99608 24080 13607 21837 46976 31358 59686 16526 83505 29144 26352 34922 97679 38576 58394 95218 40240 50465 72627 93193 20584 87854 67849 52394 68411 18313 33122 90350 97460 79307 70352 626 40067 97777 86332 66237 52528 63503 31238 69953 12917 63623 28096 77246 82499 16673 3065 82585 28156 59528 86675 14838 46298 48965 46406 46609 4253 7206 27165 89557 45780 25907 5123 33627 97679 51347 69816 67937 53986 99969 70449 88413 29101 74068 21276 22813 81284 5178 20856 9521 78392 51255 64331 76407 95926 90047 80192 9997 18565 30386 58694 75731 76262 85928 42716 78965 47939 51036 51140 67347 70652 29747 17834 85655 29951 53046 81497 16576 4316 89176 54282 84933 66751 33381 65766 54008 30629 15084 8802 82821 54056 27944 98718 96979 77511 56024 25043 58223 6041 9920 2558 58386 96951 43608 51617 5589 14393 9616 40556 63596 52154 14514 57944 91703 44207 66828 22511 52736 28794 75743 63281 40422 7382 98591 15101 64317 32616 70638 91605 35507 98840 63085 6149 34937 54896 89390 99897 88313 75155 68567 32600 63065 57931 55019 44183 87149 89720 8488 35687 99029 49642 17281 23508 37028 30890 60338 60671 24326 64133 61194 66189 22022 12140 92981 65270 21596 57600 35221 28419 36101 64922 32258 53212 23457 2957 66815 54548 24956 5015 1487 14123 75602 14019 51080 45734 12845 61265 4951 96356 15746 63617 52155 41385 48174 7651 8237 87621 34733 77996 21117 74545 36383 76139 13357 11990 38268 86286 13714 9959 58898 93579 99161 2134 73198 3023 37252 70816 83892 24803 99929 53885 90089 13906 53885 51241 21221 98281 5434 73388 86672 93782 16566 83523 40053 56522 78554 36183 2135 83495 49287 20871 47058 35093 80687 18922 54394 98129 92020 75278 70191 9756 5474 47829 90286 56552 31153 29112 84052 92992 58589 29023 17095 43912 56033 31870 71129 45542 79173 95536 90364 77942 3696 86694 85230 85811 19376 25016 1268 71834 12152 36527 99782 57746 83396 50461 96026 66365 68213 96026 246 44485 12770 24935 98657 90165 67526 83419 80331 95252 1152 4754 8613 93746 28342 76877 66857 502 49991 5742 81734 5527 67044 41894 86348 20590 19178 14404 65640 89631 32720 69122 76928 8579 82166 98588 55987 32693 34922 19937 47594 18573 32397 2144 59264 48544 96596 78510 23696 2276 8030 12854 68417 24144 55931 84197 66650 64904 53693 90294 71055 11024 12941 90635 47441 3329 52599 17834 18488 58864 88500 15957 18950 75873 78899 11936 79699 67837 41250 49046 41470 71161 18958 84151 17514 71086 3683 63793 99185 81383 67609 95747 9714 77186 26852 99065 98382 56853 27934 81335 860 68852 30553 3489 90145 88508 81505 97325 95501 90380 87546 17601 28088 26882 72488 92385 42047 69829 23037 37205 42698 65891 18326 3383 85574 16310 47775 45935 76422 22015 78475 47340 68429 13179 84065 60056 90201 91913 75426 23970 36674 21719 40151 24498 65143 69602 2198 98679 80561 37858 71503 96890 80154 87923 3236 93908 73627 78229 49670 84260 76008 41517 38434 37347 34133 46326 83243 31488 4590 19158 6443 20724 82608 2783 29752 99109 58913 29435 63146 3683 93128 45110 29813 68106 94435 42018 55111 52907 43514 90812 41663 78288 10008 14348 71470 35948 43194 45617 62684 78032 44319 73176 36820 14582 38141 34499 81293 71570 67371 64426 74435 58889 81317 86882 38876 11691 30683 99853 66436 54098 87968 83569 70492 55294 59813 6109 25496 37052 41988 78563 15750 29382 98273 63164 90275 89821 7234 76491 33709 77155 78102 72839 59996 38037 16920 43817 40499 71424 22791 91019 2720 7161 21325 8379 90971 98801 72962 19118 50010 218 98057 42317 3334 51203 2 51946 90508 35429 37890 36565 35396 99001 29613 70338 7203 94945 62744 87685 15383 1982 85612 2175 84164 10622 31739 69617 53753 69374 85051 52571 21710 79246 85646 76788 31969 92851 18371 95244 94909 68170 26573 78992 71813 90398 93483 11724 4891 25277 97559 63488 15450 72367 35270 36634 44566 83380 52179 31179 49466 28374 98587 59381 40244 91823 51470 13921 19000 47082 82126 28556 76001 49839 33556 39881 84540 6113 577 42383 52405 27834 63595 75048 22301 75464 37620 72868 63581 9033 93407 76161 73105 25968 34784 45881 28692 21872 65043 30926 26215 42590 51418 68145 9753 13010 84893 76016 77803 1577 51576 82211 92471 87707 81897 60740 30823 99274 11188 18911 8130 32913 34221 26429 95960 78066 13655 77237 16884 9823 59519 41434 41373 68141 98449 83009 60887 59401 1091 1073 66304 14690 85622 18616 65606 88979 20843 62467 85724 39002 6204 81424 6734 50776 33840 95573 91478 55802 55963 23776 73807 97961 51695 19631 9849 18223 86439 13010 48818 21878 35756 76331 31772 63882 58013 23597 37004 7594 42508 82178 84275 41941 30293 50393 57042 35180 9227 15316 31887 944 62351 79773 59883 8090 2768 7385 99609 81598 73424 73415 46164 70922 58355 55190 11457 66053 40895 76074 44364 59658 83027 36416 89900 23632 6176 92864 68660 24759 85003 56289 71266 71561 25118 3591 19600 52326 10615 42185 54079 58544 97825 79795 74251 14474 33076 10970 5145 24764 98426 5420 90945 74632 46403 67160 66359 28622 4787 96262 6879 35921 41289 89971 23537 59216 94297 85498 44955 90731 65339 58827 53144 84569 67673 34407 269 59262 97266 68310 77967 29426 58248 21390 31286 71942 55815 75577 4334 89801 65633 28009 76597 52179 83210 559 49009 26744 30454 12020 4528 91166 57584 87759 43611 39314 98180 532 28316 23880 29852 21746 27882 43986 97559 81516 74606 55958 11147 8021 7561 6522 74519 908 37101 93061 31149 98259 24959 23585 54344 27839 37956 49506 75877 78149 47548 33512 65365 92321 28955 89366 47177 65207 22109 71942 68990 84970 73192 85250 10451 1410 85415 45308 67763 63155 20810 79007 84363 37415 4350 80780 42068 30314 37733 84517 14474 35911 60471 76007 35795 71840 20832 33731 96259 90815 58767 12757 23831 4097 10627 2571 18380 71291 2705 78959 78706 61476 94043 47549 94631 66924 48867 33681 88580 42165 46427 52086 1434 63695 10065 11063 52449 70882 52931 7471 37865 30120 14268 35066 15723 82022 31841 6644 38414 73250 84296 49339 7901 43976 68244 81415 87192 48453 31112 51420 61644 99744 33653 25491 99998 40840 77592 30965 21639 23984 40587 8867 19240 82489 85130 33661 31748 55047 90065 3669 12845 95071 17138 47437 42968 77609 11414 18980 3

输出

99046