数学3

scguo · 2024-10-09 13:43:03 · 算法·理论

P1482 Cantor表（升级版）

思路

直接计算即可，不要约分！ 还有，要注意，是先输出列再输出行。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m1,z1,m2,z2;
char c;
int _gcd(int a,int b)
{
    return b?_gcd(b,a%b):a; 
} 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>m1>>c>>z1>>m2>>c>>z2;
    int m=m1*m2,z=z1*z2;
    int gcd=_gcd(m,z);
    m/=gcd,z/=gcd;
    cout<<z<<' '<<m;
    return 0;
}

U414963 分数运算

思路

这题直接套题目给的公式就行了，我用的是字符串处理，所以最后要再将数字变量中的数处理一次。也可以使用 while(cin) 来解决，代码会较短。

补充

非常实用。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int _gcd(int a,int b)
{
    return b?_gcd(b,a%b):a;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s;
    int sum=0,x=0,y=1,a,b;
    for(int i=0;i<s.size();++i)
    {
        if(s[i]=='+')
        {
            b=sum;
            sum=0;
            int xx=x*b+y*a;
            int yy=y*b;
            x=xx/_gcd(xx,yy);
            y=yy/_gcd(xx,yy);
        }
        else if(s[i]=='/')
        {
            a=sum;
            sum=0;
        }
        else
        {
            sum=sum*10+s[i]-'0';
        }
    }
    b=sum;
    sum=0;
    int xx=x*b+y*a;
    int yy=y*b;
    x=xx/_gcd(xx,yy);
    y=yy/_gcd(xx,yy);
    if(y==1) cout<<x;
    else cout<<x<<'/'<<y;
    return 0;
}

P1572 计算分数

思路

这题介绍的是 while(cin) 的方法。

我们记上一次的分子为 a，分母为 b；当前的分子为 c，分母为 d。

我们将计算出来的分子记作 sum，分母记作 sum2，求出它们的最大公因数，然后将两数都除以这个 gcd，也就是约分。

因为分母可能是负数，这是就要将分子变为负数，而分母变为正数。最后就把这个答案更新为当前的分子分母，这样，到最后的数就是答案，记得也要约分。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y;
char c;
int i,j;
char op;
int _gcd(int a,int b)
{
    return b?_gcd(b,a%b):a;
}
void cal(int a,int b,int c,int d)
{
    int sum=0;
    if(op=='-') sum=a*d-c*b;
    else sum=a*d+c*b;
    int sum2=b*d;
    int gcd=_gcd(sum,sum2);
    int ans=sum/gcd,ans2=sum2/gcd;
    if(ans2<0)
    {
        ans=-1*llabs(ans);
        ans2=llabs(ans2);
    }
    i=ans,j=ans2;
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>x>>c>>y;
    int gcd=_gcd(x,y);
    gcd=llabs(gcd);
    x/=gcd,y/=gcd;
    while(cin>>op>>i>>c>>j)
    {
        cal(x,y,i,j);
        x=i,y=j;
    }
    gcd=_gcd(x,y);
    gcd=llabs(gcd);
    x/=gcd,y/=gcd;
    if(x==0) cout<<0;
    else if(y==1) cout<<x;
    else cout<<x<<'/'<<y;
    return 0;
}

P9484 「LAOI-1」GCD

思路

这题又是一个 gcd 结论题。

很明显的可以看到，对于点 s 和 t，路线是 s \to gcd(s,t) \to t，所以，路程就是 |s - gcd(s,t)| + |t - gcd(s,t)|，化简后就是 s + t - 2 \times gcd(s,t)。

Code:

#include<bits/stdc++.h>
#define Gcd __gcd
#define int long long
using namespace std;
const int N=1e6+5;
int n,q;
int _gcd(int a,int b)
{
    return b?_gcd(b,a%b):a;
}
int lcm(int a,int b)
{
    return a*b/_gcd(a,b);
}
void solve()
{
    cin>>n>>q;
    while(q--)
    {
        int s,t;
        cin>>s>>t;
        cout<<s+t-(_gcd(s,t)*2)<<'\n';
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

P1414 又是毕业季II

思路

时间复杂度：O(n \log n)。

其实就是问是否有最大的因子，出现次数达到了 k 次，有点话就是答案。