@[贾子洋](/user/307895) 暴力行不通,想想其他办法
by LYqwq @ 2021-10-10 11:23:42
@[eric888](/user/399116) 想了其他方法,30 分求救
```cpp
#include <cstdio>
#include <iostream>
#define int long long
#define pl(n) (n / 3000000 + 1)
using namespace std;
const int len = 3000000;
int anss[505] = {
1373, 60, 0, 967, 183, 0, 303, 242, 0, 1, 114, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1011,
202, 0, 471, 470, 0, 1, 312, 0, 0, 56, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 353, 294,
0, 1, 311, 0, 0, 171, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 120, 0,
0, 98, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
template <typename T>
inline T read() {
T X = 0;
bool flag = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') flag = 0;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
X = (X << 1) + (X << 3) + ch - '0';
ch = getchar();
}
if (flag) return X;
return ~(X - 1);
}
template <typename T>
inline void write(T X) {
if (X < 0) {
putchar('-');
X = ~(X - 1);
}
int s[50], top = 0;
while (X) {
s[++top] = X % 10;
X /= 10;
}
if (!top) s[++top] = 0;
while (top) putchar(s[top--] + '0');
putchar('\n');
return;
}
inline int S(int n) {
int ans = 0;
while (n) {
ans += n % 10;
n /= 10;
}
return ans;
}
inline bool check(int n) {
if (S(n * n) == S(n) * S(n)) {
return true;
}
return false;
}
signed main() {
int l = read<int>(), r = read<int>();
int ans = 0;
if (pl(l) == pl(r)) {
for (int i = l; i <= r; i++) {
ans += check(i);
}
} else {
for (register int i = l; pl(i) == pl(l); ++i) ans += check(i);
for (register int i = pl(l) + 1; i <= pl(r) - 1; i++) ans += anss[pl(i)];
for (register int i = r; pl(i) == pl(r); --i) ans += check(i);
}
write(ans);
return 0;
}
```
by 天有不测风云 @ 2021-10-10 16:07:13
@[天有不测风云](/user/109217) 考虑看看题解?
by LYqwq @ 2021-10-10 16:08:39
@[eric888](/user/399116) ~~也许我还可以试试输出中间变量?~~
by 天有不测风云 @ 2021-10-10 16:09:52
`anss[]`是干嘛用的?
by LYqwq @ 2021-10-10 16:10:19
@[eric888](/user/399116) 每 $3000000$ 分一块,记录答案。
by 天有不测风云 @ 2021-10-10 16:12:20
@[eric888](/user/399116) $anss$ 数组是打表出来的,打表代码:
```cpp
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
template<typename T> inline T read() {
T X = 0; bool flag = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') flag = 0; ch = getchar();}
while (ch >= '0' && ch <= '9') {X = (X << 1) + (X << 3) + ch - '0'; ch = getchar();}
if (flag) return X;
return ~ (X - 1);
}
template<typename T> inline void write(T X) {
if (X < 0) {putchar('-'); X = ~ (X - 1);}
int s[50], top = 0;
while (X) {s[++top] = X % 10; X /= 10;}
if (!top) s[++top] = 0;
while (top) putchar(s[top--] + '0');
putchar(',');
putchar(' ');
return;
}
inline int S(int n) {
int ans = 0;
while (n) {
ans += n % 10;
n /= 10;
}
return ans;
}
inline bool check(int n) {
if (S(n * n) == S(n) * S(n)) {
return true;
}
return false;
}
signed main() {
for (int l = 1, r = 3000000; r <= 1000000000; l += 3000000, r += 3000000,
(r > 1000000000 && r < 1003000000) ? (r = 1000000000) : (r = r)) {
// int l = read<int>(), r = read<int>();
int ans = 0;
for (int i = l; i <= r; i++) {
ans += check(i);
}
write(ans);
// cout << l << ' ' << r << endl;
}
putchar('\n');
return 0;
}
```
打表代码是通过暴力修改的,暴力 AC:3、TLE:7.
by 天有不测风云 @ 2021-10-10 16:14:54
@[天有不测风云](/user/109217) 你可能搞复杂了,我这个蒟蒻看的眼花缭乱,我也没做过,建议学下题解的解法,我只要有题一直写不出来就去看题解,懂思路了就关掉,自己敲一遍,理清思路,还能学到不少东西
by LYqwq @ 2021-10-10 16:19:23
```cpp
#include <iostream>
using namespace std;
int fun_1(long long x)
{
int sum=0;
do
{
sum=sum+x%10;
x=x/10;
}
while (x);
return sum;
}
bool fun_2(int n)
{
int a=fun_1(n),b=fun_1((long long)n*n);
if (a*a-b) return 0;
return 1;
}
int main()
{
int l,r,i,a1,a2,a3,a4,a5,a6,a7,a8,a9,sum,ans;
bool flag=0;
cin>>l>>r;
ans=0;
if (r==1000000000) ans++;
for(a1=0;a1<=3;a1++) {for(a2=0;a2<=3;a2++) {for(a3=0;a3<=3;a3++) {for(a4=0;a4<=3;a4++) {for(a5=0;a5<=3;a5++) {for(a6=0;a6<=3;a6++) {for(a7=0;a7<=3;a7++) {for(a8=0;a8<=3;a8++) {for(a9=0;a9<=3;a9++) {sum=a1*100000000+a2*10000000+a3*1000000+a4*100000+a5*10000+a6*1000+a7*100+a8*10+a9*1; if (sum<=l-1) continue; if (sum>=r+1) {flag=1; break;} if (fun_2(sum)) ans++;} if (flag) break;} if (flag) break;} if (flag) break;} if (flag) break;} if (flag) break;} if (flag) break;} if (flag) break;} if (flag) break;}
cout<<ans<<endl;
return 0;
}
```
by dinglinxi0409 @ 2021-10-20 19:55:27