1.反素数 Antiprime
题意：找一个最小的数且约数最多的数
因为2e9+10中，一个数的约数最多有1600，所以可以暴力枚举
然后用质数枚举即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; int primes[9]={2,3,5,7,11,13,17,19,23}; int number,maxd; int n; void dfs(int u,int last,int p,int s)//u是当前第几个质数，last是质数的几次方，p是当前的数，s是约数个数 { if(s>maxd||s==maxd&&p<number) { maxd=s; number=p; } for(int i=1;i<=last;i++) { if((ll)p*primes[u]>n) break; p*=primes[u]; dfs(u+1,i,p,s*(i+1)); } } int main() { cin>>n; dfs(0,30,1,1); cout<<number<<endl; return 0; }
2.Hankson 的趣味题
题意：
- x和a0a_0a0的最大公约数是a1a_1a1；
- x和b0b_0b0的最小公倍数是b1b_1b1。，求x的个数
- 因为b1是x跟b0的最小公倍数，则直接枚举b1的所有约数即可，然后判断符不符合条件
枚举一个数的约数，可以用暴搜即可，因为一个数的约数最多只有1600个，先处理出来所有质数的s次方在求约数即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int primes[N],cnt; bool st[N]; int devide[1601],dcnt; int fcnt; struct Node { int p,s; }f[1601];//存一个质数p的s次方 void init(int n) { for(int i=2;i<=n;i++) { if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]*i<=n;j++) { st[primes[j]*i]=true; if(i%primes[j]==0) break; } } } int gcd(int a,int b) { return b?gcd(b,a%b):a; } void dfs(int u,int p)//u是当前的质数，p是当前的数 { if(u==fcnt) { devide[dcnt++]=p; return; } for(int i=0;i<=f[u].s;i++) { dfs(u+1,p); p*=f[u].p; } } void solve() { fcnt=dcnt=0; int res=0; int a0,a1,b0,b1; scanf("%d%d%d%d",&a0,&a1,&b0,&b1); int m=b1; for(int i=0;primes[i]<=m/primes[i];i++)//将b1进行分解质因数 { int p=primes[i]; if(m%p==0) { int s=0; while(m%p==0) s++,m/=p; f[fcnt++]={p,s}; } } if(m>1) f[fcnt++]={m,1}; dfs(0,1);//暴力搜索所有的约数 for(int i=0;i<dcnt;i++)//枚举所有的约数看是否符合条件 { int x=devide[i]; if(gcd(x,a0)==a1&&(ll)x*b0/gcd(x,b0)==b1) res++; } printf("%d\n",res); } int main() { init(100000); int T; scanf("%d",&T); while(T--) solve(); return 0; }
3.最大公约数
题意就是求一个超大数的最大公约数
求最大公约数用减法来做，即a=a-b,b=a 这样子，然后的用高精度减法，并且存的数是ll的数
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll base=1e15,width=15; bool cmp(vector<ll> a,vector<ll> b)//比较哪个大 { if(a.size()<b.size()) return true; if(a.size()>b.size()) return false; for(int i=a.size()-1;i>=0;i--) if(a[i]<b[i]) return true; else if(a[i]>b[i]) return false; return false; } vector<ll> sub(vector<ll> a,vector<ll> b)//高精度减法 { vector<ll> c; for(ll i=0;i<(ll)a.size();i++) { if(i>=(ll)b.size()) { if(a[i]<0) a[i]+=base,a[i+1]--; c.push_back(a[i]); } else { if(a[i]<b[i]) a[i]+=base,a[i+1]--; c.push_back(a[i]-b[i]); } } while(c.back()==0&&c.size()>1) c.pop_back(); return c; } void input(vector<ll> &a) { a.clear(); string s; cin>>s; reverse(s.begin(),s.end()); for(ll i=0;i<(ll)s.size();i+=width) { ll t=0; for(ll j=min(i+width,(ll)s.size())-1;j>=i;j--) t=t*10+(s[j]-'0'); a.push_back(t); } } void output(vector<ll> a) { for(ll i=a.size()-1;i>=0;i--) if(i==(ll)a.size()-1) printf("%lld",a[i]); else printf("%015lld",a[i]); } vector<ll> gcd(vector<ll> a,vector<ll> b) { ll t=0; vector<ll> c; c.push_back(1); while(!cmp(b,c))//假如最小的不是1，则继续减 { if(cmp(a,b)) swap(a,b);//一直让a是最大的 if(cmp(b,c)) break; a=sub(a,b);//a=a-b } return a; } int main() { vector<ll> a,b; input(a),input(b); output(gcd(a,b)); return 0; }
python做法直接秒
import math as ma a = int(input()) b = int(input()) print(ma.gcd(a, b))
4.X-factor Chain
X-factor Chain--质因数分解+组合数学_小元勋的博客-CSDN博客
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int primes[N],cnt; bool st[N]; int devide[1601],dcnt; int fcnt=0; struct { int p,s; }f[1601]; void init(int n) { for(int i=2;i<=n;i++) { if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]*i<=n;j++) { st[primes[j]*i]=true; if(i%primes[j]==0) break; } } } ll get(int n) { ll res=1; for(int i=1;i<=n;i++) res=(ll)res*i; return res; } int main() { init(N-1); int x; while(cin>>x) { dcnt=fcnt=0; for(int i=0;primes[i]<=x/primes[i];i++) { int p=primes[i]; if(x%p==0) { int s=0; while(x%p==0) s++,x/=p; f[fcnt++]={p,s}; } } if(x>1) f[fcnt++]={x,1}; sort(devide,devide+dcnt); ll len=0,k=1; for(int i=0;i<fcnt;i++) { len+=f[i].s; k*=get(f[i].s); } k=get(len)/k; cout<<len<<' '<<k<<endl; } return 0; }
5.聪明的燕姿
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e4+10; int primes[N],cnt; bool st[N]; int S; int ans[N],acnt; void init(int n) { for(int i=2;i<=n;i++) { if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]*i<=n;j++) { st[primes[j]*i]=true; if(i%primes[j]==0) break; } } } bool judge(int n) { if(n<N) return !st[n]; for(int i=0;primes[i]<=n/primes[i];i++) if(n%primes[i]==0) return false; return true; } void dfs(int u,int p,int last) { if(last==1) { ans[acnt++]=p; return; } if(last-1>primes[u>0?u:0]&&judge(last-1)) { ans[acnt++]=p*(last-1); } for(int i=u+1;primes[i]<=last/primes[i];i++) { int pm=primes[i]; for(int j=pm+1,t=pm;j<=last;t*=pm,j+=t) if(last%j==0) dfs(i,p*t,last/j); } } int main() { init(N-1); while(scanf("%d",&S)!=EOF) { acnt=0; dfs(-1,1,S); printf("%d\n",acnt); sort(ans,ans+acnt); if(acnt>=1) { for(int i=0;i<acnt;i++) printf("%d ",ans[i]); puts(""); } } return 0; }
6.Super GCD
这题跟第三题差不多，只不过数据开大了，可以直接看第三天的题解
