HDU-5970 快读卡常

2023/6/23 C++ 算法竞赛 快读 数论

还是第一次被快读卡常，痛苦

HDU-5970

题面

当代码怎么改都过不去的时候开始翻网上题解，按着题解复现了代码交上去还是TLE，一气之下把题解的代码直接交上去发现还是TLE

开始觉得不对劲，于是进HDUOJ上看曾经AC的代码，发现都是2500ms左右过的(此题限时3s)，感觉会被卡常

于是手动开启信仰优化，还是被卡；将cin换成scanf，还是被卡；试图优化计算过程，还是被卡；把一部分long long换成int，发现甚至不如全long long快，还是被卡

急了，突然想起来是不是可能在读入上还不够快，于是扒了一个快读板子，一发A了

tmd，红了

AC代码：

#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
int f(int x,int y,int &gcd,int &c)
{
    c=0;
    while(y>0)
    {
        c++;int t=x%y;x=y;y=t;
    }
    gcd=x;
    return c*x*x;
}
inline void read(int& a)
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    a = s * w;
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T;
    read(T);
    while(T--)
    {
        int n,m,p;
        read(n);read(m);read(p);
        // scanf("%lld %lld %lld",&n,&m,&p);
        int g,c;
        int ans=0;
        for(int j=1;j<=m;j++)
        {
            for(int i=1;i<=min(j,n);i++)
            {
                int temp=f(i,j,g,c);
                int K=(n-i)/j;
                int l=K%c;
                int S=K/c;
                int sum=0,res=0;
                for(int k=0;k<c;k++)
                {
                    sum+=(i*j+k*j*j)/temp;
                    if(k==l)
                        res=sum;
                }
                int x=j*j/g/g;
                ans=(ans+S*(S-1)/2*c*j*j/g/g%p+S*j*j/g/g*(l+1)%p)%p;
                ans=(ans+sum%p*S%p+res)%p;

            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

附上我这题的思路：

首先发现f(i,j)对j是有循环节的，并且长度为j，这是因为辗转相除的性质

然后观察发现n特别大，而m特别小，正好可以用循环节的性质只算一小部分来得到整体

接下来就是求和式的变形了

先设


这一步直接求和肯定是会超时的，于是想用等差数列求和公式来优化复杂度，但是这里的数又带着取整符号，所以很自然的想法就是把取整符号去掉

设

原式

看一下 的范围

设 ，则

设

于是

原式

其中 和 都可以在 复杂度内求到，外面两层循环复杂度为

img_show