解题报告 P1372 又是毕业季I

题目内容

P1372

大意:在 [1,n] 中选出 k 个数,求这 k 个数的最大的 gcd

解题思路

最近热爱写数论题不知道为什么

思路:当一个数是另一个数的倍数时,他们的 gcd 是其中小的那个数,因此想让 gcd 最大,这些选出来的数字必须满足倍数关系,又由于要选 k 个人,因此选出来人的编号应分别为 \lfloor n/k\rfloor2\lfloor n/k\rfloor3\lfloor n/k\rfloor ……所以最大的 gcd 应为 \lfloor n/k\rfloor。所以答案就是 \lfloor n/k\rfloor,复杂度 O(1)

代码:

#include <cstdio>

int main()
{
    int n,k;
    scanf("%d %d", &n, &k);
    printf("%d\n", n/k);
    return 0;
}

解题报告 P1029 gcd 和 lcm 问题

题目内容

P1029

大意:给出 x_0, y_0 ,求出满足 \gcd(P,Q)=x_0,\operatorname{lcm}(P, Q)=y_0P,Q 的个数

解题思路

挨个枚举即可,从 x_0 枚举到 y_0 ,具体思路是以下关系:

\gcd(a,b)\times\operatorname{lcm}(a,b)=\lvert ab\rvert

算出枚举到的 \gcd 然后用 x_0y_0 去除判断 lcm 是否符合条件即可。这题的数据范围理论上可以爆 int 但是他没有爆。管他的代码规范最重要。

下面的代码可以优化,但是我不想再优化了,老是 WA

#include <cstdio>
#include <cmath>
typedef unsigned long long ll;

ll gcd(ll x, ll y)
{
    if(!y) return x;
    return gcd(y,x%y);
}

int main()
{
    ll x0,y0;
    scanf("%llu %llu",&x0,&y0);
    ll prod=x0*y0,ans=0;//x_0y_0
    for(ll i=x0;i<=y0;i++)
    {
        if(!(prod%i))
        {
            ll gcdcur=gcd(i,prod/i);
            if(gcdcur==x0 && prod/gcdcur==y0)
                ans++;
        }
    }
    printf("%llu\n",ans);
    return 0;
}

解题报告 P2152 [SDOI2009]SuperGCD

题目内容

P2152

高精求两数 gcd

解题思路

使用辗转相除法求gcd的话不仅不方便实现高精,而且容易 T ,所以这里使用更相减损术。

老祖宗的方法真香

具体思路:

\begin{aligned}
\gcd(a,b)&=2\gcd(a/2,b/2)\quad&(2\mid a, 2\mid b)\
\gcd(a,b)&=\gcd(a/2,b)\quad&(2\mid a,2\not\mid b)\
\gcd(a,b)&=\gcd(a-b,b)\quad&(2\not\mid a,2\not\mid b,a>b)
\end{aligned}

依次解下去就可了,注意高精即可,代码有点麻烦,不要用递归容易爆栈

这题我一开始提交的时候莫名RE,结果发现是判断函数cmp写挂了,表示绝望调了好久qwq。

#include <cstdio>
#include <vector>
#include <cctype>
#include <algorithm>
using namespace std;

typedef vector<int> bigint;
bigint _minus(bigint, bigint);
bigint _times(bigint, bigint);
void div2(bigint&);
void print(bigint);
inline bool isodd(bigint&);

bigint _minus(bigint a, bigint b)//高精减法
{
    for(int i=0;i<b.size();i++)
    {
        a[i]=a[i]-b[i];
        if(a[i]<0)
        {
            a[i+1]--;
            a[i]+=10;
        }
    }
    for(int i=b.size();i<a.size();i++)
    {
        if(a[i]<0)
            a[i+1]--,a[i]+=10;
    }
    for(int i=a.size()-1;i>0;i--)
    {
        if(a[i])
            break;
        if(!a[i])
            a.pop_back();
    }
    return a;
}

bigint _times(bigint a, bigint b)//高精乘法
{
    bigint ans;
    int la=a.size(),lb=b.size();
    for(int i=0;i<la+lb;i++)
        ans.push_back(0);
    for(int i=0;i<lb;i++)
    {
        for(int j=0;j<la;j++)
        {
            ans[i+j]+=a[j]*b[i];
            if(ans[i+j]>=10)
            {
                ans[i+j+1]+=ans[i+j]/10;
                ans[i+j]%=10;
            }
        }
    }
    for(int i=ans.size()-1;i>0;i--)
    {
        if(ans[i])
            break;
        else
            ans.pop_back();
    }
    return ans;
}

void div2(bigint &a)
{
    for(int i=a.size()-1;i>=0;i--)
    {
        if(a[i]&1)
            a[i-1]+=10;
        a[i]/=2;
    }
    if(!a.back())
        a.pop_back();
}

bigint read()
{
    bigint ans;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        ans.push_back(c-'0');
        c=getchar();
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

void print(bigint a)
{
    for(int i=a.size()-1;i>=0;i--)
        printf("%d",a[i]);
    printf("\n");
    return;
}

inline bool isodd(bigint &a)//判断其是否为奇数
{
    return a.front()&1;
}

bool cmp(bigint a, bigint b)//return a>b
{
    if(a.size()>b.size())
        return true;
    else if(a.size()<b.size())
        return false;
    else
    {
        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;
}

int main()
{
    bigint a=read(),b=read();
    bigint tag={1},two={2};
    while(a!=b)//当a=b时zhong
    {
        if(!isodd(a) && !isodd(b))
        {//如果都是偶数那就都除以二然后标签乘二
            div2(a);
            div2(b);
            tag=_times(tag,two);
        }
        else if(!isodd(a))//如果a是偶数
            div2(a);//除以二
        else if(!isodd(b))//如果b是偶数
            div2(b);//除以二
        else
        {
            if(cmp(a,b))//判断哪个更大然后辗转相减
                a=_minus(a,b);
            else
                b=_minus(b,a);
        }
    }
    print(_times(a,tag));//返回的是最终结果乘上tag
    return 0;
}