输入数据包括2个数：a, b，中间用空格分隔。（1≤a≤b≤10^9）
输出a~b里每个数字的有趣约数个数之和。
1 10
4
标解：http://www.51nod.com/contest/problemSolution.html#!problemId=1742
里面的式子改写一开始一直不明白，稍微有点明白了，说说另一种想的方法吧
最暴力的是枚举数字再枚举约数看看是不是平方因子数了
一个简单的优化是枚举约数i,约数i的贡献(倍数的数量)就是[n/i]
但还是会T
一个巧妙的想法是我们枚举是几倍，当前枚举的是i倍，那么满足i倍<=n的数字就是<=[n/i],答案加上<=[n/i]的平方因子数的个数，就是标解中最后的式子了
计算的时候用了两次分块n/(i*i)和n/i做到O(n^2/3)
然而比只一次分块还慢是什么鬼？sqrt的问题吗
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=1e5+5; inline int read(){ char c=getchar();ll x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; } int a,b; bool notp[N]; int p[N],mu[N]; void sieve(int n){ mu[1]=1; for(int i=2;i<=n;i++){ if(!notp[i]) p[++p[0]]=i,mu[i]=-1; for(int j=1;j<=p[0]&&i*p[j]<=n;j++){ notp[i*p[j]]=1; if(i%p[j]==0) break; mu[i*p[j]]=-mu[i]; } } //for(int i=1;i<=n;i++) printf("mu %d %d\n",i,mu[i]); //for(int i=1;i<=n;i++) mu[i]+=mu[i-1]; } //int F(int n){ // int _=0,r=0,m=sqrt(n); // for(int i=1;i<=m;i=r+1){ // r=n/(n/(i*i)); // _+=n/(i*i)*(mu[r]-mu[i-1]); // } // return n-_; //} int f(int n){ int _=0,m=sqrt(n); for(int i=1;i<=m;i++) _+=n/(i*i)*mu[i]; return n-_; } ll S(int n){//printf("n %d\n",n); ll ans=0;int r=0; for(int i=1;i<=n;i=r+1){ r=n/(n/i); ans+=(r-i+1)*f(n/i); //printf("f %d %d %d %d\n",n/i,i,r,f(n/i)); } return ans; } int main(){ //freopen("in","r",stdin); a=read();b=read(); sieve(sqrt(b)+1); printf("%lld",S(b)-S(a-1)); }
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=1e5+5; inline int read(){ char c=getchar();ll x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; } int a,b; bool notp[N]; int p[N],mu[N]; void sieve(int n){ mu[1]=1; for(int i=2;i<=n;i++){ if(!notp[i]) p[++p[0]]=i,mu[i]=-1; for(int j=1;j<=p[0]&&i*p[j]<=n;j++){ notp[i*p[j]]=1; if(i%p[j]==0) break; mu[i*p[j]]=-mu[i]; } } //for(int i=1;i<=n;i++) printf("mu %d %d\n",i,mu[i]); for(int i=1;i<=n;i++) mu[i]+=mu[i-1]; } int F(int n){//printf("F %d\n",n); int _=0,r=0,m=sqrt(n); for(int i=1;i<=m;i=r+1){ r=sqrt(n/(n/(i*i)));//printf("r %d\n",r); _+=n/(i*i)*(mu[r]-mu[i-1]); } return n-_; } ll S(int n){//printf("n %d\n",n); ll ans=0;int r=0; for(int i=1;i<=n;i=r+1){ r=n/(n/i); ans+=(r-i+1)*F(n/i); //printf("F %d %d %d %d\n",n/i,i,r,F(n/i)); } return ans; } int main(){ //freopen("in","r",stdin); a=read();b=read(); sieve(sqrt(b)+1); printf("%lld",S(b)-S(a-1)); }
原文：http://www.cnblogs.com/candy99/p/6367375.html