//模板
__int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
void print(__int128 x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

//模板解释
void print(__int128 x){
    if(x<0)putchar('-'),x=-x; // 不是必要的，也可以写if(x<0)cout<<"-",x=-x;
    if(x>9)print(x/10);// 此处一定是x/10，不是x/=10
    putchar(x%10+'0');// 不是必要的，进行一个格式强转就可以输出出来了//cout<<(int)x%10;
}
// 注意，此处是利用递归的倒叙输出。从低位往高位递归，那么会先从高位输出。

T304806 202301B 铺地毯​​https://www.luogu.com.cn/problem/T304806?contestId=96572​​

B https://codeforces.com/problemset/problem/1731/B

思路：沿着对角线走是贡献最大的，因此每一次都是走对角线+一格向下。总体就是

Codeforces Round #841 (Div. 2) and Divide by Zero 2022_数学

整道题的难点其实就是怎么求  平方的和。

这个需要公式，百度一下就有了

我是用了__int128， 范围是2的39次方 够这个2^27次方。

__int128可以像正常的数那样参与加减乘除取模运算，还有赋值运算。

注意__int128，不能用cin cout scanf print。直接读到__int128需要快读模板和输出模板的。

​​__int128 read(){​​

​​    __int128 x=0,f=1;​​

​​    char ch=getchar();​​

​​    while(!isdigit(ch)&&ch!='-')ch=getchar();​​

​​    if(ch=='-')f=-1,ch=getchar();​​

​​    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();​​

​​    return f*x;​​

​​}​​

​​void print(__int128 x){​​

​​    if(x<0)putchar('-'),x=-x;​​

​​    if(x>9)print(x/10);​​

​​    putchar(x%10+'0');​​

​​}​​

注意codeforces上__int128需要选对语言才能用