【BZOJ 4635】数论小测验

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4635
数据生成器:http://paste.ubuntu.com/24360378/
神犇题解:http://www.cnblogs.com/clrs97/p/5625508.html

解题报告

对于第一问,显然可以用莫比乌斯反演做到$O(Tm)$

对于第二问,考虑枚举$k$,然后$10^3$以内的数最多有$4$种不同的质因数
于是搞一个状压$DP$,用矩阵快速幂优化
单词询问时间复杂度:$O(32m^2 + 32^3 log (n))$
看起来蛮有希望过的,但卡了一下午常也没有卡过 QwQ

正解的话,我们可以学习Claris用容斥
具体来讲枚举$k$,然后枚举$k$的每一个质因数是否满足条件
然后配合一点预处理之类的,就可以做到$O(m^2 + m \log m)$了

Code

这份代码在BZOJ被卡常了 QwQ

#include<bits/stdc++.h>
#define LL long long
using namespace std; 
 
const int MOD = 1000000007;
const int N = 10000009;
const int M = 32;
 
int n,m,SZ,s1[N],hc[N],to[1001];
int tot,pri[N>>3],mu[N]; bool vis[N];
 
inline int read() {
    char c=getchar(); int f=1,ret=0;
    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;
}
 
inline int Pow(int w, int t) {
    int ret = 1;
    for (;t;t>>=1,w=(LL)w*w%MOD) 
        if (t&1) ret=(LL)ret*w%MOD;
    return ret;
}
 
inline void GetMu() {
    mu[1] = 1;
    for (int i=2;i<N;i++) {
        if (!vis[i]) mu[i] = -1, pri[++tot] = i;
        for (int j=1;j<=tot&&pri[j]*i<N;j++) {
            vis[i*pri[j]] = 1;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        } 
        mu[i] = mu[i-1] + mu[i];
    } 
}
 
inline int cal(int mx) {
    int ret = 0;
    for (int l=1,r,tmp;l<=mx;l=r+1) {
        r = mx / (mx / l);
        tmp = (LL)(mu[r] - mu[l-1]) * hc[mx/l] % MOD;
        ret = (ret + tmp) % MOD;
    }
    return (ret + MOD) % MOD;
}
 
struct Matrix{
    int a[M][M];
    inline Matrix() {memset(a,0,sizeof(a));}
    inline Matrix(const Matrix *A) {
        for (int i=0;i<M;i++) for (int j=0;j<M;j++) a[i][j] = A->a[i][j];
	}
    inline Matrix(int x) {
        memset(a,0,sizeof(a)); 
        for (int i=0;i<SZ;i++) a[i][i] = x;
    } 
    inline void operator *= (const Matrix &A) {
        Matrix ret; 
        for (int i=0,*t1,*t3;i<SZ;i++) {
        	t1 = ret.a[i]; const int *t2 = A.a[i];
			for (int j=0;j<SZ;j++) {
				t3 = a[j];
				for (int k=0;k<SZ;k+=4) { 
					t1[k] = (t1[k] + (LL)t3[k] * t2[j]) % MOD; 
					t1[k+1] = (t1[k+1] + (LL)t3[k+1] * t2[j]) % MOD; 
					t1[k+2] = (t1[k+2] + (LL)t3[k+2] * t2[j]) % MOD;
					t1[k+3] = (t1[k+3] + (LL)t3[k+3] * t2[j]) % MOD;
				}
			}
		}
        for (int i=0;i<SZ;i++) for (int j=0;j<SZ;j++) a[i][j] = ret.a[i][j];
    }
    inline Matrix operator ^ (int t) {
        Matrix ret(1),w(this);
        for (;t;t>>=1,w*=w) if (t&1) ret*=w;
        return ret;
    }
}ans,trans;
 
inline int solve(int w) {
    tot = 0; 
    for (int i=2,tmp=w;i<=tmp;i++) {
        if (tmp % i == 0) {
            pri[++tot] = i; tmp /= i;
            while (tmp % i == 0) pri[tot] *= i, tmp /= i;
        }
    } 
    ans = Matrix(); trans = Matrix(); 
    ans.a[0][0] = 1; SZ = 1 << tot;
    memset(to,0,sizeof(to));
    for (int i=1,t=1,ww;ww=pri[i],i<=tot;i++,t<<=1) 
		for (int j=ww;j<=m;j+=ww) to[j] |= t;
    for (int i=1,tt;tt=to[i],i<=m;i++) {
        for (int p=0,ww;ww=p,p<SZ;p++) 
            ++trans.a[p|tt][p];
    }
    trans = trans ^ n;
    ans *= trans;
    return ans.a[SZ-1][0];
}
 
int main() {
    int T = read(), type = read();
    if (type == 1) {
        GetMu(); 
        for (int t=1,vout;vout=0,t<=T;t++) {
            n = read(); m = read(); 
            int L = read(), R = read();
            for (int l=1,r;l<=m;l=r+1) {
                r = m / (m / l);
                hc[m / l] = Pow(m / l, n);
            }
            for (int l=L,r,tmp;l<=R;l=r+1) {
                r = m / (m / l); tmp = cal(m / l);
                vout = (vout + (min(r,R)-max(L,l)+1ll) * tmp) % MOD;
            }           
            printf("%d\n",vout);
        }
    } else if (type == 2) {
        for (int t=1,vout,l,r;vout=0,t<=T;t++) {
            n = read(); m = read(); l = read(), r = read();
            for (int w=l;w<=r;w++) vout = (vout + solve(w)) % MOD;
            printf("%d\n",vout);
        }
    }
    return 0;
}

338 thoughts to “【BZOJ 4635】数论小测验”

  1. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored material stylish.
    nonetheless, you command get got an edginess over that you wish
    be delivering the following. unwell unquestionably come more formerly again since exactly the same nearly very often inside case you
    shield this increase.

  2. I’m really loving the theme/design of your blog. Do you ever run into any
    browser compatibility issues? A handful of my blog visitors have complained
    about my blog not working correctly in Explorer but looks great in Firefox.
    Do you have any advice to help fix this issue?

  3. Your style is really unique in comparison to other people I’ve read stuff from.
    Many thanks for posting when you’ve got the opportunity, Guess I will just bookmark this site.

  4. I’ve been browsing on-line more than three hours as of late, yet I by no means found any attention-grabbing article like yours.

    It is beautiful worth sufficient for me. In my view, if all website owners and bloggers made good content material as you did,
    the web will be much more helpful than ever before.

  5. If you wish for to take a great deal from this paragraph then you have to apply such methods to your won website.

  6. Hey there! This is my 1st comment here so I just wanted
    to give a quick shout out and say I truly enjoy reading through your blog posts.

    Can you recommend any other blogs/websites/forums that go over the same topics?

    Many thanks!

  7. Greate article. Keep writing such kind of info on your blog.

    Im really impressed by your site.
    Hello there, You have performed an incredible job.
    I will certainly digg it and in my opinion suggest to my friends.
    I am sure they will be benefited from this site.

  8. Heya i’m for the first time here. I found this board and
    I find It truly helpful & it helped me out much.
    I’m hoping to offer one thing back and aid others such as you helped me.

  9. Today, I went to the beachfront with my children. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.

    There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is completely
    off topic but I had to tell someone!

  10. Hi there! I could have sworn I’ve been to this blog before but after browsing through
    some of the post I realized it’s new to me.

    Anyways, I’m definitely delighted I found it and I’ll be bookmarking and checking back often!

  11. I am now not certain the place you are getting your information,
    however good topic. I must spend a while learning much more or working out more.
    Thank you for magnificent information I used
    to be on the lookout for this info for my mission.

  12. You really make it appear so easy along with your
    presentation but I in finding this topic to be actually something that I feel
    I would by no means understand. It seems too complex and
    very large for me. I’m taking a look ahead on your subsequent put up, I will attempt to
    get the hold of it!

  13. My coder is trying to convince me to move to .net from PHP.

    I have always disliked the idea because of the costs.

    But he’s tryiong none the less. I’ve been using
    WordPress on a variety of websites for about a year and am concerned about switching to another platform.
    I have heard very good things about blogengine.net.

    Is there a way I can transfer all my wordpress content into it?
    Any help would be really appreciated!

  14. Heya i am for the first time here. I came across
    this board and I find It truly useful & it helped me out much.
    I hope to give something back and help others like you helped me.

  15. Howdy! This is my 1st comment here so I just wanted
    to give a quick shout out and tell you I genuinely enjoy reading your blog posts.
    Can you suggest any other blogs/websites/forums that go over the
    same topics? Appreciate it!

  16. Have you ever considered publishing an ebook or guest authoring on other websites?
    I have a blog based on the same ideas you discuss and would really like to have
    you share some stories/information. I know my visitors would enjoy your work.
    If you are even remotely interested, feel free to shoot me an email.

  17. I used to be suggested this website via my cousin. I’m no longer sure whether this
    put up is written by him as no one else realize such distinct
    about my difficulty. You’re incredible! Thank you!

  18. A person essentially lend a hand to make significantly articles I would state.
    That is the first time I frequented your website page and to this point?
    I surprised with the research you made to create this particular submit
    amazing. Magnificent task!

  19. Hello there, I discovered your web site by means of Google at the
    same time as looking for a comparable topic, your web site got here
    up, it seems to be good. I’ve bookmarked it in my google bookmarks.

    Hi there, just became aware of your weblog via Google,
    and found that it is truly informative. I’m gonna watch out for
    brussels. I will be grateful if you happen to continue this in future.
    A lot of people shall be benefited out of your writing.
    Cheers!

  20. Hi there! I could have sworn I’ve visited this website before but after going through many of the articles
    I realized it’s new to me. Anyways, I’m certainly delighted I found it and I’ll be book-marking it and checking
    back frequently!

  21. Thanks for the marvelous posting! I certainly
    enjoyed reading it, you may be a great author.I will ensure
    that I bookmark your blog and definitely will come back
    later in life. I want to encourage continue
    your great posts, have a nice morning!

  22. I’ve been surfing on-line greater than 3 hours lately,
    yet I by no means discovered any fascinating article like yours.
    It is pretty worth sufficient for me. In my view,
    if all website owners and bloggers made good content material as you probably did, the internet
    can be much more useful than ever before.

  23. Hey there! This is my first comment here so I just wanted to give a
    quick shout out and say I genuinely enjoy reading through your posts.
    Can you suggest any other blogs/websites/forums that go over the same subjects?
    Thanks a lot!

  24. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to
    my blog that automatically tweet my newest twitter updates.

    I’ve been looking for a plug-in like this for
    quite some time and was hoping maybe you would have some experience with something like this.
    Please let me know if you run into anything. I
    truly enjoy reading your blog and I look forward to your new updates.

  25. Hey! Quick question that’s entirely off topic. Do you know how to make
    your site mobile friendly? My web site looks weird when browsing from
    my iphone4. I’m trying to find a template or plugin that might be able to correct this problem.
    If you have any suggestions, please share. Cheers!

  26. Hey! I know this is kind of off-topic but I needed
    to ask. Does running a well-established website such as yours
    take a large amount of work? I am brand new to operating a blog but I
    do write in my journal every day. I’d like to start a blog so
    I will be able to share my personal experience and thoughts
    online. Please let me know if you have any kind of suggestions or tips for
    new aspiring blog owners. Thankyou!

  27. First of all I would like to say wonderful blog! I had a quick question that I’d like to ask if you do not mind.
    I was interested to find out how you center yourself and clear your mind prior
    to writing. I’ve had difficulty clearing my thoughts
    in getting my ideas out. I truly do take pleasure in writing
    however it just seems like the first 10 to 15 minutes
    are usually wasted just trying to figure out how to begin.
    Any ideas or tips? Appreciate it!

  28. Hey there! This post could not be written any better!
    Reading through this post reminds me of my good old room mate!
    He always kept talking about this. I will forward this post to him.
    Fairly certain he will have a good read. Many thanks for sharing!

  29. I am not certain the place you are getting your info, but good topic.
    I needs to spend some time studying more or understanding more.
    Thank you for wonderful information I was searching for this information for my
    mission.

  30. I’ve been browsing online more than 4 hours today, yet I never found any interesting article like yours.

    It’s pretty worth enough for me. In my opinion, if all website owners and bloggers made good content
    as you did, the net will be a lot more useful than ever before.

  31. I have been exploring for a bit for any high quality articles or weblog posts in this
    kind of area . Exploring in Yahoo I ultimately stumbled upon this web site.

    Reading this info So i am satisfied to express that
    I’ve a very just right uncanny feeling I discovered just what I needed.
    I so much indubitably will make sure to do not put out of your mind this site and provides it a glance regularly.

  32. Hey There. I discovered your weblog using msn. That is a
    really well written article. I’ll be sure to bookmark
    it and return to learn more of your helpful info. Thank
    you for the post. I’ll certainly return.

  33. First of all I would like to say excellent blog! I had a quick question in which I’d like to ask if you do not mind.
    I was interested to find out how you center
    yourself and clear your head prior to writing.
    I’ve had a difficult time clearing my mind in getting my
    ideas out. I truly do take pleasure in writing but it just seems like the first 10
    to 15 minutes tend to be wasted simply just trying to figure out how
    to begin. Any ideas or hints? Cheers!

  34. Undeniably believe that which you stated. Your favorite reason seemed to be on the internet the
    easiest thing to be aware of. I say to you, I certainly
    get annoyed while people think about worries that they plainly do not know about.
    You managed to hit the nail upon the top and defined out the whole thing without having side-effects , people can take a signal.
    Will likely be back to get more. Thanks

  35. Nice post. I was checking constantly this blog and I’m impressed!
    Extremely useful information specially the last part 🙂 I
    care for such information much. I was looking for this certain info for a very long time.
    Thank you and good luck.

  36. Hi there, I discovered your web site by means of Google while searching
    for a similar topic, your website came up, it seems to be good.
    I have bookmarked it in my google bookmarks.
    Hi there, simply changed into aware of your weblog thru Google, and located that it’s really informative.
    I’m going to be careful for brussels. I will appreciate
    for those who proceed this in future. Many other people will probably be benefited out of your writing.
    Cheers!

  37. Heya i’m for the first time here. I found this board and
    I find It truly useful & it helped me out a lot. I’m hoping to
    present something back and help others like you helped me.

  38. hello there and thank you for your info – I’ve definitely picked up anything
    new from right here. I did however expertise
    a few technical points using this website, as I experienced to reload the website a lot of times previous
    to I could get it to load properly. I had been wondering if your web hosting is OK?
    Not that I’m complaining, but sluggish loading instances times will sometimes affect your placement in google and could damage your high-quality score
    if ads and marketing with Adwords. Anyway I am
    adding this RSS to my e-mail and could look out for
    much more of your respective fascinating content. Make sure
    you update this again very soon.

  39. Hey! This post couldn’t be written any better! Reading
    through this post reminds me of my good old room mate!
    He always kept chatting about this. I will forward this post to him.

    Pretty sure he will have a good read. Thank you for sharing!

  40. Wonderful website. A lot of useful information here.
    I’m sending it to some buddies ans additionally sharing in delicious.
    And certainly, thank you in your effort!

  41. Fantastic goods from you, man. I have understand your stuff previous to and you’re just
    extremely wonderful. I actually like what you’ve acquired here, really like what you’re stating and the way in which you say it.
    You make it enjoyable and you still take care of to keep it smart.
    I can’t wait to read far more from you. This is really a terrific web site.

  42. I am sure this piece of writing has touched all the internet viewers, its really really fastidious piece of writing
    on building up new weblog.

  43. Valuable information. Lucky me I discovered your web
    site by accident, and I’m stunned why this accident did not happened
    earlier! I bookmarked it.

  44. Hello there, There’s no doubt that your blog might be having browser compatibility issues.
    Whenever I look at your web site in Safari, it looks fine but when opening in IE, it has some overlapping issues.

    I just wanted to give you a quick heads up! Other than that, excellent website!

  45. Greetings, There’s no doubt that your site could possibly
    be having internet browser compatibility issues.

    Whenever I take a look at your web site in Safari, it looks fine
    however when opening in IE, it has some overlapping issues.
    I just wanted to give you a quick heads up! Other than that, fantastic
    site!

  46. Everything is very open with a clear explanation of the issues.
    It was definitely informative. Your website is very useful.
    Thank you for sharing!

  47. wonderful points altogether, you just received a
    logo new reader. What might you suggest in regards
    to your submit that you just made a few days ago?
    Any certain?

  48. Amazing blog! Is your theme custom made or did you download it from somewhere?
    A theme like yours with a few simple tweeks would really make
    my blog stand out. Please let me know where you got your design. Kudos

  49. Hey there! Do you use Twitter? I’d like to
    follow you if that would be okay. I’m definitely enjoying
    your blog and look forward to new updates.

  50. I think this is among the most vital info for me. And i am glad reading your article. But want to remark on some general things, The website style is ideal, the articles is really great : D. Good job, cheers

  51. My partner and I stumbled over here from adifferent page and thought I should check things out.I like what I see so now i am following you. Look forward to going over your web page for a second time.

  52. When I initially commented I clicked the „Notify me when new comments are added“ checkbox and now each time a comment is added I get three emails with the same comment. Is there any way you can remove me from that service? Many thanks!

  53. fantastic submit, very informative. I wonder why the opposite specialists of this sector do not notice this. You should proceed your writing. I am sure, you have a huge readers’ base already!

  54. Remarkable page as well as convenient in order to comprehend justification. Exactly how can We start gaining concur in order to put up part from the guide during my coming bulletin? Getting good credit score for you the actual journalist as well as backlink towards the websites won’t be considered a challenge.

  55. Simply want to say your article is as astounding.The clearness in your post is simply spectacular and i can assume you are an expert on this subject.Well with your permission allow me to grab your feed to keep up to date with forthcoming post.Thanks a million and please keep up the enjoyable work.

  56. Great blog! Do you have any hints for aspiring writers?I’m hoping to start my own blog soon but I’m a little lost on everything.Would you recommend starting with a free platform like WordPress or go for a paid option? Thereare so many options out there that I’m completely confused ..Any tips? Thank you!

  57. Undeniably believe that which you said. Your favorite reason seemed to be at the internet the simplest thing to be mindful of. I say to you, I definitely get irked while other people consider issues that they just do not understand about. You managed to hit the nail upon the highest and also outlined out the whole thing with no need side-effects , other folks can take a signal. Will probably be again to get more. Thank you|

  58. Thank you, I have just been searching for info approximately this subject for ages and yours is the greatest I’ve discovered so far. However, what about the bottom line? Are you certain about the source?|

  59. Great post. I was checking continuously this blog and I’m impressed! Extremely useful info particularly the last part 🙂 I care for such information much. I was looking for this particular info for a long time. Thank you and best of luck.|

  60. After going over a number of the articles on your website, I truly appreciate your way of writing a blog. I book-marked it to my bookmark site list and will be checking back soon. Please visit my website as well and let me know how you feel.|

  61. Hi there! I simply want to offer you a big thumbs up for your great info you’ve got right here on this post. I will be coming back to your blog for more soon.

  62. It is truly a nice and helpful piece of info. I’m satisfied that you simply shared this useful information with us. Please stay us informed like this. Thanks for sharing.|

  63. Its like you read my mind! You appear to know a lot about this, like you wrote the book in it or something. I think that you can do with a few pics to drive the message home a bit, but other than that, this is excellent blog. An excellent read. I will certainly be back.

  64. Thank you for another wonderful post. Where else may anyone get that kind of info in such an ideal approach of writing? I’ve a presentation subsequent week, and I’m at the search for such info.|

  65. Thanks for ones marvelous posting! I definitely enjoyed reading it, you are a great author. I will always bookmark your blog and will come back in the foreseeable future. I want to encourage continue your great writing, have a nice holiday weekend!|

  66. Undeniably believe that which you said. Your favorite justification seemed to be on the net the simplest thing to be aware of. I say to you, I certainly get irked while people consider worries that they just do not know about. You managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people can take a signal. Will probably be back to get more. Thanks|

Leave a Reply

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