【Codeforces 55D】Beautiful numbers







总的来说,我似乎爱上了第三种写法 = ̄ω ̄=

#define LL long long
using namespace std;

int MOD[]={1,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520};
int pos[2530],lcm[50][50],sta[20]; 
LL f[20][50][2530];

LL GCD(LL a, LL b) {return b?GCD(b,a%b):a;}
LL LCM(LL a, LL b) {return a/GCD(a,b)*b;}

LL DFS(int t, int lm, int mod, bool top) {
	if (t == 0) {
		return !(mod % MOD[lm]);
	} else if (~f[t][lm][mod] && !top) {
		return f[t][lm][mod];	
	} else {
		LL ret = 0;
		for (int i=0,ty=(top>0?sta[t]:9),tmp;i<=ty;i++) {
			tmp = lcm[lm][i];
			ret += DFS(t-1,tmp,(mod*10+i)%2520,top&&i==sta[t]);
		return top?ret:f[t][lm][mod] = ret;

inline LL cal(LL lim) {
	int cnt = 0;
	while (lim) {
		sta[++cnt] = lim % 10;
		lim /= 10;
	return DFS(cnt,1,0,1);

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;

int main(){
	for (int i=1;i<=48;i++) {
		pos[MOD[i]] = i;
	for (int i=0;i<=48;i++) {
		for (int j=0;j<=48;j++) {
			lcm[i][j] = pos[LCM(MOD[i],MOD[j])];
	for (int T=read();T;--T) {
		LL l = read(), r = read();
	return 0;

28 thoughts to “【Codeforces 55D】Beautiful numbers”

  1. I’ll right away grasp your rss as I can’t to find your email subscription link
    or newsletter service. Do you have any? Please let me recognize in order that I could
    subscribe. Thanks.

  2. Wow that was strange. I just wrote an extremely long comment but after I clicked submit my comment didn’t appear.
    Grrrr… well I’m not writing all that over again. Anyhow, just wanted to say great blog!

  3. I loved as much as you’ll receive carried out right here.
    The sketch is attractive, your authored material stylish.

    nonetheless, you command get got an shakiness over that
    you wish be delivering the following. unwell unquestionably
    come more formerly again as exactly the same nearly a
    lot often inside case you shield this increase.

  4. Hi there fantastic blog! Does running a blog similar to this take
    a massive amount work? I’ve absolutely no expertise in computer
    programming but I had been hoping to start my own blog soon. Anyways, should you have any suggestions or techniques for new blog owners please share.
    I know this is off subject but I just needed to ask.
    Many thanks!

  5. Having read this I believed it was rather informative.
    I appreciate you taking the time and effort to put this short article together.
    I once again find myself personally spending
    way too much time both reading and leaving comments.
    But so what, it was still worth it!

  6. What i do not understood is in truth how you’re now not really much more well-appreciated than you
    may be right now. You’re very intelligent.
    You recognize therefore considerably on the subject
    of this matter, made me in my opinion imagine it from numerous various angles.
    Its like women and men don’t seem to be interested until it is
    something to do with Woman gaga! Your personal stuffs outstanding.
    At all times deal with it up!

  7. You’ve made some good points there. I looked on the net to learn more about the issue and found most individuals will go along with your views on this website.

  8. My husband and i felt quite happy that John could finish off his studies from the precious recommendations he had through your web page. It is now and again perplexing just to be releasing secrets most people might have been making money from. And now we recognize we now have the blog owner to be grateful to for that. These illustrations you made, the straightforward site menu, the friendships you can assist to instill – it’s mostly astounding, and it is facilitating our son in addition to our family do think the subject is satisfying, and that is pretty indispensable. Many thanks for the whole thing!

  9. Hello just wanted to give you a quick heads up. The words in your content seem to be running off the screen in Internet explorer.
    I’m not sure if this is a format issue or something to do with internet browser compatibility but I figured I’d post to let you know.
    The style and design look great though! Hope you get the problem fixed soon. Thanks

  10. What’s up it’s me, I am also visiting this web site daily, this
    website is actually good and the visitors are really sharing pleasant thoughts.

  11. Hi my loved one! I want to say that this post is awesome, nice written and
    come with almost all important infos. I would like to peer extra posts like this .

  12. Good web site you have here.. It’s difficult to find good quality writing
    like yours these days. I honestly appreciate people like you!
    Take care!!

  13. Thank you a lot for sharing this with all of us you really recognise what you are speaking approximately!
    Bookmarked. Please also talk over with my website =). We could
    have a link alternate contract among us

  14. Very nice post. I just stumbled upon your blog and wanted to mention that I
    have really enjoyed browsing your blog posts.

    After all I’ll be subscribing to your rss feed and I hope
    you write again soon!

  15. Hey! I know this is kind of off topic but I was wondering which
    blog platform are you using for this website? I’m getting sick
    and tired of WordPress because I’ve had problems with hackers and I’m looking at options for another platform.
    I would be fantastic if you could point me in the direction of a good platform.

  16. great issues altogether, you just gained a new reader.
    What might you recommend about your submit that you simply made some days in the past?
    Any positive?

  17. This is really interesting, You are a very skilled blogger. I’ve joined your rss feed and look forward to seeking more of your great post. Also, I’ve shared your website in my social networks!

Leave a Reply

Your email address will not be published. Required fields are marked *