自动搬运

查看原文

来自洛谷，原作者为

	Jiyuu_no_Tsubasa 高い自由の翼、進撃する巨人の心

搬运于2025-08-24 21:27:04，当前版本为作者最后更新于2021-01-23 09:18:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题是一道经典的枚举题，

考察写码技巧，

若同时枚举 $a$ 与 $b$，

时间复杂度 $O(1.2*10^{13})$

必定超时。

但我们可以想到另一种做法：

只枚举 $n$，

然后枚举所有与 $n$ 构成循环数的的 $m$，

再判断 $m$ 是否在答案范围内，

这样就极大地缩减了时间复杂度。

那么如何枚举 $m$ 呢？

很简单，

因为从 $a$ 循环到 $b$

位数都相同（题面中有。

我们可以预先算出循环范围的位数 $s$，

再预处理出 $10$ 的 $0$ 到 $6$ 次方。

然后每次取出数的最后一位 $*10^{s-1}$，

再加上这个数 $/10$ 即可。

举个例子：

$12345$，

取最后一位得 $5$，

位数 $s$ 为 $5$，

$5*10^{s-1}=5*10^4=50000$

$12345/10=1234$

$50000+1234=51234$

$51234$ 即为 $12345$ 的第一个解

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long ans;
int p[7]={1,10,100,1000,10000,100000,1000000};
int main(){
    int a; cin>>a;
    int b; cin>>b;
    int s=0,v=a;
    while(v) v/=10,s++;//计算位数
    for(int i=a,n,m;i<b;i++){//枚举n
        n=i;
        m=(n%10)*p[s-1]+n/10;//如上文计算m
        while(n!=m){//若n==m，则m枚举完毕
            ans+=n<m&&m<=b;//即符合条件，ans++
            m=(m%10)*p[s-1]+m/10;//枚举m
        }
    }
	cout<<ans;
	return 0;
}

完结撒花