A. Enlarge GCD
题意:给你N个数让你从中删除最小的数使得所有数的公因子变大,如果不能变大则输出-1
题解:先求出所有数的最大公因子,
这儿我用的是STL里面的函数__gcd(a,b),需要注意的是这个函数前面有两条下划线,然后函数是泛型的。和gcd是一样的。
然后我用线性筛求出所有的质数,根据唯一分解定理将每个数含有的所有质因数全部算出来,然后统计出现次数最多的质因数,然后输出。
#include <bits/stdc++.h>
const int MAXN = 15000000;
using namespace std;
int n,cnt,g,a[MAXN+5],p[MAXN+5],sum[MAXN+5],ans = MAXN;
bool vis[MAXN+5];
inline void pre()
{
for(int i = 2;i <= MAXN;i++){
if(!vis[i]){
p[++cnt] = i;
}
for(int j = 1;j <= cnt && i * p[j] <= MAXN;j++){
vis[i*p[j]] = true;
}
}
}
inline int read(){
int x = 0;char ch = getchar();
while(ch < '0' || '9' < ch){ch = getchar();}
while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
return x;
}
int main()
{
pre();n = read();
for(int i = 1;i <= n;i++) a[i] = read();
g = 0;
for(int i = 1;i <= n;i++) g = __gcd(g,a[i]);
for(int i = 1;i <= n;i++) a[i] /= g;
for(int i = 1;i <= n;i++){
for(int j = 1;p[j]*p[j] <= a[i];j++)
if(!(a[i]%p[j])){
sum[p[j]]++;
while(!(a[i]%p[j]))a[i] /= p[j];
}
if(a[i] != 1) sum[a[i]]++;
}
for(int i=2; i<=MAXN; i++){
ans = min(ans, n-sum[i]);
}
if(ans == n) printf("-1\n");
else printf("%d\n",ans);
return 0;
}
B. Little C Loves 3 II
题意:问你在N*M的棋盘中最多按照规定最多放下多少的棋子。每次放两个棋子而两个棋子的曼哈顿距离为3
题解:我看的一个大佬的博客写的。
Tiw_Air_OAO
//https://blog.csdn.net/Tiw_Air_Op1721/article/details/82811681#_73
#include <bits/stdc++.h>
using namespace std;
long long n,m;
int main(){
scanf("%lld %lld",&n,&m);
if(n > m) swap(n,m);
if(n == 1){
if(!(m%6)) printf("%lld",m);
else if((m%6) <= 3) printf("%lld",m-(m%6));
else printf("%lld",m-6+(m%6));
}
else if(n == 2){
if(m == 2) printf("0");
else if(m == 3) printf("4");
else if(m == 7) printf("12");
else printf("%lld",m*2);
}
else
{
if(n & 1 && m & 1) printf("%lld",n*m-1);
else printf("%lld",n*m);
}
}