// f(n)表示 n的约数和 不包括自己
// 给你一个m 求1 到 100万里面 f(n)<=m 的个数
// 那么首先要用筛选求出所有出 f(n)
// 然后就好办了
// 写好后 看见别人好快 去百度了下 发现有用二分的 用了下 快了 100Ms 不过 数据越大 二分优势越明显
#include <iostream> #include <math.h> #include <map> #include <stack> #include <queue> #include <vector> #include <algorithm> #include <stdio.h> #include <string.h> using namespace std; #define maxm 10010 #define maxn 1000010 int 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]<m) n++; printf("%d ",n); } return 0; }
二分 求解
#include <iostream> #include <math.h> #include <map> #include <stack> #include <queue> #include <vector> #include <algorithm> #include <stdio.h> #include <string.h> using namespace std; #define maxm 10010 #define maxn 1000010 int 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 ",l-1); } return 0; }