第六个点TLE了,请问怎么改才能AC?

P1865 A % B Problem

~~打表~~
by lndjy @ 2020-01-09 17:39:14


@[水题淹死的鱼](/user/196899) 我想知道我的为什么错了
by HITACorz @ 2020-01-10 16:36:15


@[JryACtrying](/user/52067) 不需要快读快输,数组开始就不必全部标为1啦,是素数表示为0,否则表示为1得了。
by OIers_Convolution @ 2020-02-04 17:05:58


每次读入范围都去遍历会很慢,不如刚开始把从0~i(i=0,1,2,3...)的素数个数存下来,到时候相减就行,我是这样搞得```cpp ``` isnotprime[0]=1,isnotprime[1]=1; for(int i=2;i<=m;i++) { if(!isnotprime[i]) { prime[++prime[0]]=i; number[i]=number[i-1]+1;//number:记录0~i的素数个数 } else { number[i]=number[i-1]; } for(int j=1;j<=prime[0]&&i*prime[j]<=m;j++) { isnotprime[i*prime[j]]=1; if(i%prime[j]==0)break; } } //将个数记录完后读入范围,number[r]-number[l-1]即可
by 龙卡 @ 2020-02-09 23:06:00


|