题解 P1611 【循环的数字】

· · 题解

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

考察写码技巧，

若同时枚举 a 与 b，

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

必定超时。

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

只枚举 n，

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

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

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

那么如何枚举 m 呢？

很简单，

因为从 a 循环到 b

位数都相同（题面中有。

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

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

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

再加上这个数 /10 即可。

举个例子：

取最后一位得 $5$， 位数 $s$ 为 $5$， $5*10^{s-1}=5*10^4=50000 12345/10=1234 50000+1234=51234 代码如下： ``` #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; } ``` ## 完结撒花