话说要做一道奇形怪状的DP的前提是知道这是一道奇形怪状的DP

openjudge7239

我一直以为这是一道正常的数论，结果

题解原文（全）:

dp[i]表示使得最大公约数是i最小使用多少数。

简洁明快所以脑部一下状态转移方程：dp[gcd(v[i],j)]=min(dp[gcd(v[i],j)],dp[j]+1)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;


int gcd(int a,int b)
{
	int c;
	while (a!=0)
	{
		c=a;
		a=b%a;
		b=c;
	}
	return b;
}


int main()
{
	ios_base::sync_with_stdio(false);
	int v[702],dp[10002],n,g;
	memset(dp,0x3f,sizeof(dp));
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>v[i];
		dp[v[i]]=1;
	}
	for (int i=0;i<n;i++)
	{
		for (int j=1;j<10002;j++)
		{
			if (dp[j]!=0x3f3f3f3f)
			{
				int s=gcd(v[i],j);
				if (dp[s]>dp[j]+1)
				{
					dp[s]=dp[j]+1;
				}
			};
		}
	}
	g=v[0];
	for (int i=1;i<n;i++)
	{
		g=gcd(g,v[i]);
	}
	cout<<n-dp[g];
	return 0;
}