做网站编辑器,西湖app开发公司,十大采购平台,html网站中文模板下载A Hard Problem
题意#xff1a;
给定一个n#xff0c;要求找到最小的正数k#xff0c;使得在集合T中任意选K个数#xff0c;其中存在两个不同的u和v#xff0c;u是v的因子
题解#xff1a;
一开始想偏了#xff0c;往质因数方向想了#xff0c;然后因为1e9的以内的…A Hard Problem
题意
给定一个n要求找到最小的正数k使得在集合T中任意选K个数其中存在两个不同的u和vu是v的因子
题解
一开始想偏了往质因数方向想了然后因为1e9的以内的质数无法求而放弃 这个题其实很简单我们想对于一个数n离他最近的因子(不考虑本身)就是n/2也就说nn-1n-2…n/21这些数两两之间不存在因子关系因为n最近的都到n/2所以k最小就是(n1)/21,n除以2向上取整1因为必须1才保证正好存在因子关系
代码:
#includebits/stdc.h
using namespace std;
const int maxn1e89;
typedef long long ll;
mapint,inttag;
mapint,intPri;
mapint,intans;
int tot0;
void prime()
{tag[1]tag[0]1;int N100000;for(ll i2;iN;i){if(!tag[i])Pri[tot]i;ans[i]tot1;for(ll j1;jtoti*Pri[j]N;j){tag[i*Pri[j]]1;if(i%Pri[j]0)break;}}
}
int main(){int t;cint;//prime();int q1;while(t--){int n;cinn;cout(n1)/21endl;//coutqans[q]endl;}return 0;
}
