[Title Description]
Counting game is a popular leisure game. Everyone participating in the game should take turns to report the number in a certain order, but if the number of the next report is a multiple of 7, or the decimal representation contains the number 7, you must skip this number, otherwise you will lose the game.
On a sunny afternoon, Xiao r and Xiao z, who had just finished the SP C20nn game, were bored and played the counting game. But it's easy to calculate when there are only two people playing, so they haven't decided the outcome for a long time. At this time, little z had a flash of inspiration and decided to strengthen the game: any number containing the number 7 in the decimal system cannot report all its multiples!
Formally, let p(x) indicate whether the decimal representation of X contains the number 7. If so, p(x) = 1, otherwise p(x) = 0. Then a positive integer x cannot be reported if and only if there are positive integers y and z such that x = yz and p(y) = 1.
For example, if small r reports 6, because 7 cannot be reported, small z needs to report 8 next; If the small r reports 33, it is due to 34 = 17 × 2 ，35 = 7 × 5 can not be reported, small z next need to report 36; If small r reports 69, because the number of 70 ∼ 79 contains 7, small z needs to report 80 next.
Now the last number of Xiao r reports x. Xiao z wants to quickly calculate how much he wants to report next, but he soon finds that this game is much more difficult than the original game, so he needs your help. Of course, if the x reported by small R cannot be reported by itself, you should also react quickly. Only when small R loses.
Since Xiao r and Xiao z played the game for a long time, you also need to answer many questions of Xiao z.
[input]
In line 1, a positive integer T indicates the number of small z queries.
Next, in line T, each line has a positive integer x, which represents the number reported by small r this time.
[output]
There are T lines in total, and each line is an integer. If the number reported this time by small r cannot be reported, output − 1, otherwise output the number reported next by small z.
[input example]
4 6 33 69 300
[output example]
8 36 80 ‐1
This question should be the only one among several questions that can be done by the popularization group.
The title is that you write an sv function to initialize the record table, and then query the output answer in the table. This is basically the case of prime sieve, but the judgment time is different:
bool Sv(int k){
while(k){
if(k%10==7)return true;
k/=10;
}
return false;
}void Init(){
for(int i=1;i<=MXX;i++){
if(!table[i]&&Sv(i)){
for(int j=1;i*j<=MXX;j++){
table[i*j]=true;
}
}
}
}The function means to detect something that has not been detected. The form is the same as the prime sieve, but MXX cannot open the root because it is not a simple multiplication and cannot correctly handle the situation of 100007 (casually, assuming it is a prime). table is the result and accelerates:
#include<iostream>
#include<cmath>
using namespace std;
//Put each number in the bucket
const int MXX=1e7+11;
bool table[MXX];
bool Sv(int k){
while(k){
if(k%10==7)return true;
k/=10;
}
return false;
}
void Init(){
for(int i=1;i<=MXX;i++){
if(!table[i]&&Sv(i)){
for(int j=1;i*j<=MXX;j++){
table[i*j]=true;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t,x;
Init();
cin>>t;
while(t--){
cin>>x;
if(table[x]){
cout<<"-1\n";
}else{
x++;
while(table[x]){ //This search is a waste of time
x++;
}
cout<<x<<"\n";
}
}
return 0;
}Such code can pass 7 of 10 test points, and the other 7 times out. It has been noted in the code, and the query is too time-consuming: the title actually gives a very clear prompt. Think about it for yourself, 7, 14, 17, 21, 27... 70-79, 87... When there are more digits, the length of continuous band 7 will be very long.
How can we simplify this by looking for things in a loop every time? We already have the flag table. We only need to change it a little: the flag table records the current number, but instead points to the next non-7 related number. In this way, we only need to preprocess the data here and add a cycle, which can be read directly in the future:
#include<iostream>
#include<cmath>
using namespace std;
const int MXX=1e7+11;
int table[MXX];
bool Sv(int k){
while(k){
if(k%10==7)return true;
k/=10;
}
return false;
}
void Init(){
for(int i=1;i<=MXX;i++){
if(!table[i]&&Sv(i)){
for(int j=1;i*j<=MXX;j++){
table[i*j]=true;
}
}
}
//What is the next number that is not 7 related
int last=1;
for(int i=2;i<=MXX;i++){
if(!table[i]){
table[last]=i;last=i;
}else{
table[i]=i;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t,x;
Init();
cin>>t;
while(t--){
cin>>x;
if(table[x]==x){
cout<<"-1\n";
}else{
cout<<table[x]<<"\n";
}
}
return 0;
}Details:
The first non 7 related number after 10000000 is 100000010