SPOJ ODDDIV - Odd Numbers of Divisors

2019-11-08 01:32:21

字体：大中小

来源：转载

供稿：网友

ODDDIV - Odd Numbers of Divisors number-theory Given a positive odd integer K and two positive integers low and high, determine how many integers between low and high contain exactly K divisors.

Input

The first line of the input contains a positive integer C (0

#include<iostream>#include<cstring>#include<algorithm>#include<vector>#include<cmath>using namespace std;typedef long long LL;const int MAXN=100000+10;int PRime[MAXN+1];int ans[MAXN];vector<int> vec[MAXN];void getprime(){ memset(prime,0,sizeof(prime)); for(int i=2;i<MAXN;i++) { if(!prime[i]) { prime[++prime[0]]=i; } for(int j=1;j<=prime[0]&&prime[j]<MAXN/i;j++) { prime[prime[j]*i]=1; if(i%prime[j]==0) break; } }}//用vec[i]存下所有的，有i个约数的完全平方数void getfac(int x){ int tmp=x; int ans=1; for(int i=1;prime[i]*prime[i]<=tmp;i++) { int cnt=0; if(tmp%prime[i]==0) { while(tmp%prime[i]==0) { cnt++; tmp/=prime[i]; } } if(cnt) ans*=(2*cnt+1); } if(tmp!=1) { ans*=3; } vec[ans].push_back(x);}int main(){ getprime(); for(int i=1;i<MAXN;i++) { getfac(i); } int T; cin>>T; int k; LL low,high; while(T--) { cin>>k>>low>>high; int pos1=upper_bound(vec[k].begin(),vec[k].end(),(int)sqrt(high)+1e-8)-vec[k].begin()-1; int pos2=upper_bound(vec[k].begin(),vec[k].end(),(int)(sqrt(low)+1-1e-8)-1)-vec[k].begin()-1; cout<<pos1-pos2<<endl; } return 0;}

上一篇：c语言多级指针

下一篇：Mac 安装scrapy框架