牛客刷题之数学基础-约数

比赛地址

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

目录

1.反素数 Antiprime

2.Hankson 的趣味题

3.最大公约数

4.X-factor Chain

5.聪明的燕姿

6.Super GCD

---

 

1.反素数 Antiprime

题意：找一个最小的数且约数最多的数

因为2e9+10中，一个数的约数最多有1600，所以可以暴力枚举

然后用质数枚举即可

#include
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
    {
        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<
   return 0;
}

2.Hankson 的趣味题

题意：

• x和a0a_0a0​的最大公约数是a1a_1a1​；
• x和b0b_0b0​的最小公倍数是b1b_1b1​。，求x的个数
• 因为b1是x跟b0的最小公倍数，则直接枚举b1的所有约数即可，然后判断符不符合条件

枚举一个数的约数，可以用暴搜即可，因为一个数的约数最多只有1600个，先处理出来所有质数的s次方在求约数即可 

#include
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//枚举所有的约数看是否符合条件
    {
        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
using namespace std;
typedef long long ll;
ll base=1e15,width=15;
bool cmp(vector a,vector b)//比较哪个大
{
    if(a.size()size()) return true;
    if(a.size()>b.size()) return false;
    for(int i=a.size()-1;i>=0;i--)
        if(a[i]return true;
        else if(a[i]>b[i]) return false;
    return false;
}
vector sub(vector a,vector b)//高精度减法
{
    vector 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]1]--;
            c.push_back(a[i]-b[i]);
        }
    }
    while(c.back()==0&&c.size()>1) c.pop_back();
    return c;
}
void input(vector &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 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 gcd(vector a,vector b)
{
    ll t=0;
    vector 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 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
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
       {
           len+=f[i].s;
            k*=get(f[i].s);
       }
       k=get(len)/k;
       cout<' '<
   }
   return 0;
}

5.聪明的燕姿

AcWing 1296. 聪明的燕姿 - AcWing

#include
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(nreturn !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;iprintf("%d ",ans[i]);
            puts("");
       }
   }
   return 0;
}

6.Super GCD

这题跟第三题差不多，只不过数据开大了，可以直接看第三天的题解
​