本文共 2259 字，大约阅读时间需要 7 分钟。
// f(n)表示 n的约数和 不包括自己 // 给你一个m 求1 到 100万里面 f(n)<=m 的个数 // 那么首先要用筛选求出所有出 f(n) // 然后就好办了 // 写好后 看见别人好快 去百度了下 发现有用二分的 用了下 快了 100Ms 不过 数据越大 二分优势越明显 #include #include #include #include #include #include #include #include #include using namespace std;#define maxm 10010#define maxn 1000010int prim[maxn/3],p;bool f[maxn];int gcd(int a,int b){ int r; while(r=a%b){a=b;b=r;} return b;}bool isp(int n){ if(n==2) return true; if(n%2==0||n==1) return false; int m=(int)(sqrt(n+1.0)); for(int i=3;i<=m;i+=2) if(n%i==0) return false; return true;}int getprime(){ int i,j; f[1]=true; for(i=4;i<=maxn;i+=2) f[i]=true; int m=(int)(sqrt(maxn+1.0)); for(i=3;i<=m;i+=2){ for(j=i*i;j<=maxn;j+=i) f[j]=true; } for(i=1;i<=maxn;i++) if(!f[i]) prim[p++]=i;}int sum[maxn];void sum_divisor(int n){ int i,j; int m=(int)(sqrt(n+1.0)); for(i=2;i<=n/2;i++) for(j=i+i;j<=n;j+=i) sum[j]+=i;}int main(){ int n; int m; int i,k; sum_divisor(maxn); while(scanf("%d",&m)!=EOF){ n=0; for(i=1;i<=1000000;i++) if(sum[i]
二分 求解
#include #include #include #include #include #include #include #include #include using namespace std;#define maxm 10010#define maxn 1000010int prim[maxn/3],p;bool f[maxn];int gcd(int a,int b){ int r; while(r=a%b){a=b;b=r;} return b;}bool isp(int n){ if(n==2) return true; if(n%2==0||n==1) return false; int m=(int)(sqrt(n+1.0)); for(int i=3;i<=m;i+=2) if(n%i==0) return false; return true;}int getprime(){ int i,j; f[1]=true; for(i=4;i<=maxn;i+=2) f[i]=true; int m=(int)(sqrt(maxn+1.0)); for(i=3;i<=m;i+=2){ for(j=i*i;j<=maxn;j+=i) f[j]=true; } for(i=1;i<=maxn;i++) if(!f[i]) prim[p++]=i;}int sum[maxn];void sum_divisor(int n){ int i,j; int m=(int)(sqrt(n+1.0)); for(i=2;i<=n/2;i++) for(j=i+i;j<=n;j+=i) sum[j]+=i;}int main(){ int n; int m; int i,k; sum_divisor(maxn); sort(sum+1,sum+1000000+1); while(scanf("%d",&m)!=EOF){ int l=1,r=1000000,mid; while(l<=r){ mid=(l+r)>>1; if(sum[mid]+1>m) r=mid-1; else if(sum[mid]+1<=m) l=mid+1; // printf("%d ",sum[mid]+1); getchar(); }; printf("%d\n",l-1); } return 0;}
转载于:https://www.cnblogs.com/372465774y/p/3208878.html