题目中说,7的倍数以及含有7的数与其倍数都不能报出
我们可以观察一下含有7的数(暂时不需要管其倍数)的特征
前几个满足条件的数依次为7、17、27、37、47、57、67、70、71、72、73、74、75、76、77、78、79、87、97、107、117
观察之后,我们能够发现,从7开始,依次增加10的数中都含有7,于是我们可以把这些数及其倍数标记一下。
70、170、270这种从70开始,依次增加100的数中也都含有7,同样也标记一下。
我们还能发现,从700开始,依次增加1000的数也含有7,我们可以发现一个规律:
从7*(10^n)开始,依次增加10*(10^n)的数中都含有7,依次标记它们还有它们的倍数即可。
同时,我们还能发现,类似70、71、72、73、74、75、76、77、78、79这种,从70*(10^n)+100*(10^n)*m到80*(10^n)-1+100*(10^n)*m的数中都含有7,同样也标记一下。
之后,我们倒着循环,将答案存放在f数组里,之后循环输出即可。
[C++] 纯文本查看 复制代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;
unsigned int q[200005];
int f[10000055]; // 存放答案的数组
bitset<10000055> vis; // 是否为不能报出的数,使用bitset可节省内存并加快速度
char buf[1000000], * p1 = buf, * p2 = buf;
inline char nc() { // 读取一个字符
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int& x) // 快读,不解释
{
x = 0;
char s = nc();
while (s < '0' || s > '9') s = nc();
while (s >= '0' && s <= '9') { x = (x << 3) + (x << 1) + (s ^ 48); s = nc(); }
}
inline void read(unsigned int& x)
{
x = 0;
char s = nc();
while (s < '0' || s > '9') s = nc();
while (s >= '0' && s <= '9') { x = (x << 3) + (x << 1) + (s ^ 48); s = nc(); }
}
inline void print(int x) // 快输,也不解释
{
if (x == -1) {
fputs("-1", stdout);
return;
}
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
int main() {
register int t;
read(t);
unsigned int start = 0; // 最大需要循环到的值
for (unsigned int i = 0; i < t; ++i) {
read(q[i]);
start = max(start, q[i]);
}
start += 50;
unsigned int a = 7, b = 10, c = 8, d;
for (unsigned int i = 0; i < 7; ++i) {
for (unsigned int j = a; j <= start; j += b) {
if (vis[j]) continue;
for (unsigned int k = j; k <= start; k += j) {
vis[k] = true; // 标记
}
}
if (i >= 1) {
unsigned int v = 0;
while (true) {
if (a + v * b > start) break;
d = c + v * b;
if (d > start) d = start;
for (unsigned int j = a + v * b; j < d; ++j) {
if (vis[j]) continue;
for (unsigned int k = j; k <= start; k += j) {
vis[k] = true; // 标记
}
}
++v;
}
}
a *= 10;
b *= 10;
c *= 10;
}
unsigned int last = 0;
for (unsigned int i = start; i > 0; i--) { // 将答案存放到f数组里
if (!vis[i]) {
f[i] = last;
last = i;
}
else
f[i] = -1;
}
for (unsigned int i = 0; i < t; ++i) {
print(f[q[i]]); // 输出
putchar('\n');
}
}
|