牛客算法周周练6

B-华华对月月的忠诚

给出A,B,N,且F[1]=A,F[2]=B,F[n]=F[n-1]+F[n-2];
求解gcd(F[n],F[n+1])==?
gcd(F[n],F[n+1])=gcd(F[n+1],F[n]%F[n+1])=gcd(F[n+1],F[n])
gcd(F[n],F[n+1]%F[n])=gcd(F[n],(F[n]+F[n-1])%F[n])=gcd(F[n],F[n-1])
gcd(F[n],F[n+1])=gcd(F[n+1],F[n])=gcd(F[n],F[n-1])=gcd(F[n-1],F[n-2])=......=gcd(B,A)
也就是说gcd(F[n],F[n+1])=gcd(B,A)

#include <bits/stdc++.h>
using namespace std;
long long a,b;
string n;
long long gcd(long long a,long long b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    cin>>a>>b>>n;
    cout<<gcd(a,b);
}

C-Game

举个例子 32=4 $图片说明$ 8=2 $图片说明$ 2 $图片说明$ 8=2 $图片说明$ 2 $图片说明$ 2 $图片说明$ 4=2 $图片说明$ 2 $图片说明$ 2 $图片说明$ 2 $图片说明$ 2
或32=2 $图片说明$ 16=2 $图片说明$ 2 $图片说明$ 8=2 $图片说明$ 2 $图片说明$ 2 $图片说明$ 2 $图片说明$ 4=2 $图片说明$ 2 $图片说明$ 2 $图片说明$ 2 $图片说明$ 2
也就是说不管怎么取集合中的数，将其分解为两个非1因子，最多能分解的次数为n转换成为其最小的因子的个数
因此只要求出n的最小因子的个数（此文中最小因子指的是将某个数分解成不能再分解的因子的乘积）
最后根据因子个数的奇偶判断胜者

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin>>n;
    int i=2,c=0;
    while(n>1)
    {
        if(n%i==0)
        {
            c++;
            n/=i;
        }
        else
            i++;
    }
    if(c%2)
        cout<<"Nancy";
    else
        cout<<"Johnson";
}

D-挖沟

任意两点之间连通，且存在最小值将所有点连通
也就是最小生成树的模板题

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct num{
  int u,v,weigh;
}x[500005];
long long res=0;
bool cmp(struct num a,struct num b)
{
    return a.weigh<b.weigh;
}
int f[500005];
int fi(int x){return f[x]==x?x:f[x]=fi(f[x]);}
void un(int x,int y){int u=f[x],v=f[y];if(u!=v)f[v]=u;}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>x[i].u>>x[i].v>>x[i].weigh;
    sort(x,x+m,cmp);
    for(int i=0;i<=n;i++)f[i]=i;
    for(int i=0;i<m;i++)
    {
        if(fi(x[i].u)!=fi(x[i].v))
        {
            un(x[i].u,x[i].v);
            res=res+x[i].weigh;
        }
    }
    cout<<res;
}