题解 | #无穷无尽的小数#

D.无穷无尽的小数

手搓两个示例，不难发现，循环节长度为;答案为这个长度的字符串减法。

构造为我们要进行加减的字符串。还要确定的点在于最后要不要再，比如循环节分别为跟的时候，最后得到的循环节为而不是，而在循环节分别为跟的时候，最后得到的循环节为。仔细观察不难发现当的时候，不需要向前借位，即不用再。而在的时候，设跟为当时进行加减的那一位小数，从这一位开始，前面的所有位置都要向前借一位，具体示例可参考跟。

然后就是具体的字符串减法了，从最后一位开始进行减法，用进行记录有没有向前借位，利用存储答案，最后翻转即为答案。

#include<bits/stdc++.h>
#define int long long
#define double long double
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dep(i,r,l) for(int i=r;i>=l;i--)
#define lowbit(x) ((x)&-(x))
#define pb push_back
#define fi first
#define se second
#define endl '\n'
const int MAX=0x3f3f3f3f3f3f3f3f;
const int INF=-0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int MOD=998244353;
const int N=2e5+9;
// const int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
// const int fx[8][2]={{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};
// const int fx[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{2,-1},{1,2},{2,1}};
using namespace std;
/*----------------------------global variable & function----------------------------*/
int n,m;
string a,b;
/*---------------------------------------code---------------------------------------*/
void tyx()
{
    cin>>n>>m;
    cin>>a;
    cin>>b;
    string s="";
    int t=lcm(n,m);
    string l1="",l2="";
    rep(i,1,t/n){
        l1+=a;
    }
    rep(i,1,t/m){
        l2+=b;
    }
    int cnt=0;
    bool g=true;
    rep(i,0,t-1){
        int x1=l1[i]-'0';
        int x2=l2[i]-'0';
        if(x1>x2) break;
        if(x1<x2){
            g=false;
            break;
        }
    }
    dep(i,t-1,0){
        int r1=l1[i]-'0';
        int r2=l2[i]-'0';
        if(cnt==1) r1--;
        if(i==t-1&&!g) r1--;
        if(r1>=r2){
            s+=to_string(r1-r2);
            cnt=0;
        }
        else{
            s+=to_string(r1+10-r2);
            cnt=1;
        }
    }
    reverse(s.begin(),s.end());
    cout<<t<<endl;
    cout<<s<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        tyx();
    }
    return 0;
}