Zut

A - gcd,求因子(裸题)

A题链接

#include<iostream> //A - gcd,求因子(裸题) #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 4e5 + 10; ll a[N]; int n; ll gcd(ll x, ll y) { if (y == 0)return x; return gcd(y, x % y); }; int main() { cin>> n; for (int i = 1; i <= n; i++)cin >> a[i]; ll res = a[1]; for (int i = 2; i <=n; i++) { res = gcd(a[i], res); } ll ans=0; for (ll i = 1; i <=res / i; i++) { if (res % i == 0) { if (res / i == i)ans++; else ans += 2; } } cout << ans << endl; }

B 质因数分解

题意：对一个正整数n可进行多次mul和sqrl操作，求最小值和对应的操作次数。

#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N = 1e6 + 5; typedef long long ll; int n, cnt, ans = 1; vector<int> vec; int main() { cin >> n; int maxn = 0; for (int i = 2; i <=n ; i++) { cnt = 0; if (n % i == 0)ans *= i; while (n % i==0) { n /= i; cnt++; } while (1 << maxn < cnt)maxn++; if (cnt)vec.push_back(cnt); } int flag = 0; for (int i = 0; i < vec.size(); i++) if (vec[i] != (1 << maxn))flag = 1; cout << ans << " " << flag + maxn; return 0; }

C素数筛 埃式筛

题意:给n个数,给出m组l,r.设i为l-r之间的一个质数,这个质数能被n个数中的x个数整除,令f(i)=x.求l-r区间中所有f(i)的总和.

#include <cstdio> #include <iostream> using namespace std; const int Max=10000010; int n,cnt[Max],vis[Max],is[Max],m,a,b,t; void init() { for(int i=2;i<Max;i++) { if(!is[i]) { cnt[i]+=vis[i]; for(int j=i+i;j<Max;j+=i) is[j]=1,cnt[i]+=vis[j]; } } for(int i=2;i<Max;i++) cnt[i]+=cnt[i-1]; } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&t); vis[t]++; } init(); scanf("%d",&m); while(m--) { scanf("%d%d",&a,&b); if(a>Max-1) a=Max-1; if(b>Max-1) b=Max-1; printf("%d\n",cnt[b]-cnt[a-1]); } return 0; }

D - gcd,lcm,因子

题意：给出a，b，求出k使得lcm(a+k，b+k)最小

#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 1e4 + 10; ll f[maxn]; int cnt = 0; void slove(ll n) { for(ll i = 1; i * i <= n; ++i) { if(n % i == 0) { f[cnt++] = i; if(i != n / i) f[cnt++] = n / i; } } } ll gcd(ll a, ll b) { return b == 0 ? a: gcd(b, a % b); } int main() { ll a, b; cin >> a >> b; if(a > b) swap(a, b); ll c = b - a; slove(c); ll m = a * b / gcd(a, b); ll ans = 0; for(int i = 0; i < cnt; ++i) { ll tmp = a + (f[i] - a % f[i]) % f[i]; tmp *= (b + (f[i] - a % f[i]) % f[i]) / gcd(c, tmp); if(tmp < m) { ans = (f[i] - a % f[i]) % f[i]; m = tmp; } } cout << ans << endl; return 0; }

E - 素数筛,gcd,质因数分解

题意：给出n个数，问最少去掉几个数可以让剩下的数的最大公因数比n个数的最大公因数大。

首先求出n个数的gcd，让每个数除以gcd后得到的数就没有了公因数； 但是其中的某几个数还可能会有公因数； 由于互质的gcd最小，所以尽可能保留gcd!=1的数，剩下的就是要去掉的数了

#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N = 3e5 + 10; const int MAX = 1.5e7 + 10; ll gcd(ll a,ll b) { return b == 0 ? a : gcd(b, a % b); } ll a[N],cnt[MAX],gd; bool prime[MAX]; int main() { int n; cin >> n; cin >> a[1]; gd = a[1]; for (int i = 2; i <= n; i++)cin >> a[i], gd = gcd(gd, a[i]); for (int i = 1; i <= n; i++) cnt[a[i] / gd]++; int ans = 0; for (int i = 2; i <MAX; i++) { if (!prime[i]) { int sum = 0; for (int j = i; j <MAX; j += i) sum += cnt[j],prime[j] = true; ans = max(ans, sum); } } if (ans)cout << n - ans << endl; else cout << "-1" << endl; return 0; }