P1662 数7

P1662 数7

首先我们可以知道,这样对于每次报数的判定转向是 (O(logV)) 的。

然后因为这里的数据范围非常大,并且答案可以递推,我们可以考虑分段打表。

所以我们每 (10^6) 一个表,然后相当于最后的询问一定落在一个块里,我们调用块首的答案然后开始接着模拟跳即可。

代码:

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
int n,ans,pos,tmp,t[105][2]={{0,1},{117,-1},{522,-1},{1161,1},{887,1},{156,-1},{364,-1},{841,1},{841,-1},{1246,-1},{548,1},{274,1},{880,-1},{1088,-1},{228,1},{345,-1},{750,-1},{52,-1},{52,1},{658,-1},{866,-1},{6,1},{123,-1},{528,-1},{1167,1},{893,1},{162,-1},{370,1},{370,1},{487,-1},{892,-1},{194,1},{1257,1},{526,-1},{734,-1},{1211,1},{1328,-1},{396,1},{396,-1},{670,-1},{64,1},{1193,1},{716,-1},{599,1},{194,1},{892,-1},{1166,-1},{560,-1},{560,1},{83,-1},{1303,1},{898,1},{259,-1},{533,-1},{1264,1},{1056,1},{579,-1},{462,-1},{462,1},{1160,-1},{97,-1},{828,1},{620,1},{143,-1},{26,1},{958,1},{319,-1},{593,1},{593,-1},{801,-1},{1278,1},{1278,1},{1278,1},{1278,1},{1278,1},{1278,1},{1278,1},{1278,1},{1278,1},{1278,1},{1278,-1},{215,-1},{946,1},{738,1},{261,-1},{144,1},{1076,1},{437,1},{437,-1},{1168,1},{960,1},{483,-1},{366,1},{1298,1},{659,-1},{933,-1},{327,1},{119,-1},{119,-1},{2,1},{934,1}};
bool Check(int x){
	if(x%7==0) return true;
	tmp=x;
	while(tmp){
		if(tmp%10==7) return true;
		tmp/=10;
	}
	return false;
}
int main(){
	read(n);
	tmp=n/10000000;pos=1;
	ans=t[tmp][0],pos=t[tmp][1];
	for(int i=tmp*10000000+1;i<=n;++i){
		ans=(ans+pos+1337)%1337;
		if(Check(i)) pos=-pos;
	}
	write(ans?ans:1337);
	return 0;
}

原文地址:https://www.cnblogs.com/Akmaey/p/14668733.html