扫描网站漏洞的软件,红色大气网站,腾讯企业邮箱登录入口手机版,网站建设实训的认识正题
luogu CF1305F 题目大意
给你n个数#xff0c;每次操作可以使一个数1或-1#xff0c;让你用最小的操作数使所有数的gcd1 解题思路
显然把所有数都修改为偶数可以得到 2|gcd#xff0c;且步数 ≤n\leq n≤n
对于其它方案#xff0c;至少有一半的数修改次数小于…正题
luogu CF1305F 题目大意
给你n个数每次操作可以使一个数1或-1让你用最小的操作数使所有数的gcd1 解题思路
显然把所有数都修改为偶数可以得到 2|gcd且步数 ≤n\leq n≤n
对于其它方案至少有一半的数修改次数小于1如果不满足那其他数大于一半且步数 ≥2\geq 2≥2所以步数大于n不如前面的方案
所以每次随机一个数进行质因数分解然后考虑每个质因数作为gcd的最小步数gcd可能是合数但是只用满足有一个质因子就好了
这样每一次操作得到正确答案的概率最小是 12\frac{1}{2}21如果取 k 个数得到正确答案的概率就是 2k−12k\frac{2^k-1}{2^k}2k2k−1 code
#includemap
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 200210
#define NN 1000010
using namespace std;
int n,w,p[NN];
ll x,ans,a[N],prime[NN];
mapll,intpp;
void work()
{for(int i2;i1e6;i){if(!p[i])prime[w]i;for(int j1;jwi*prime[j]1e6;j){p[i*prime[j]]1;if(i%prime[j]0)break;}}return;
}
ll get(ll x)
{if(pp[x])return ans;pp[x]1;ll sum0;for(int i1;insumans;i)summin((a[i]x?a[i]%x:x),x-a[i]%x);return sum;
}
void solve(ll x)
{for(int i1;iwprime[i]*prime[i]x;i)if(x%prime[i]0){ansmin(ans,get(prime[i]));while(x%prime[i]0)x/prime[i];}if(x1)ansmin(ans,get(x));return;
}
int main()
{srand(2018729);scanf(%d,n);work();for(int i1;in;i){scanf(%lld,a[i]);if(a[i]1)ans;}for(int k1;kmin(20,n/2)ans;k){xrand()*rand()%n1;while(p[x])xrand()*rand()%n1;p[x]1;solve(a[x]);solve(a[x]-1);solve(a[x]1);}printf(%lld,ans);return 0;
}
