BZOJ 2671 Calc

Myth丶恋晨 2021-12-19 18:39 245阅读 0赞

# 题目链接 #

[https://lydsy.com/JudgeOnline/problem.php?id=2671][https_lydsy.com_JudgeOnline_problem.php_id_2671]

# 题解 #

对于一对(a,b)(a,b)(a,b)满足a+b∣aba+b\\mid aba\+b∣ab，假设d=gcd⁡(a,b),a=xd,b=ydd=\\gcd(a,b),a=xd,b=ydd=gcd(a,b),a=xd,b=yd，那么  
xd+yd∣xyd2x+y∣xydx+y∣d xd+yd\\mid xyd^2\\\\ x+y\\mid xyd\\\\ x+y\\mid d xd\+yd∣xyd2x\+y∣xydx\+y∣d  
设m=⌊n⌋m=\\lfloor\\sqrt\{n\}\\rfloorm=⌊n⌋答案就是  
∑j=1m∑i=1j−1⌊ni+j⌋\[gcd⁡(i,j)=1\]=∑d=1mμ(d)∑j=1⌊m/d⌋∑i=1j−1⌊nd2(i+j)⌋ \\begin\{aligned\} & \\sum\_\{j=1\}^\{m\}\\sum\_\{i=1\}^\{j-1\}\\lfloor\\frac\{n\}\{i+j\}\\rfloor \[\\gcd(i,j)=1\]\\\\ = & \\sum\_\{d=1\}^\{m\}\\mu(d)\\sum\_\{j=1\}^\{\\lfloor m/d\\rfloor\}\\sum\_\{i=1\}^\{j-1\}\\lfloor\\frac\{n\}\{d^2(i+j)\}\\rfloor \\end\{aligned\} =j=1∑mi=1∑j−1⌊i\+jn⌋\[gcd(i,j)=1\]d=1∑mμ(d)j=1∑⌊m/d⌋i=1∑j−1⌊d2(i\+j)n⌋  
复杂度大概是O(n3/4)O(n^\{3/4\})O(n3/4)的，这个请大家自行证明。

# 代码 #

#include <cmath>
    #include <cstdio>
    #include <algorithm>
    
    int read()
    { 
      int x=0,f=1;
      char ch=getchar();
      while((ch<'0')||(ch>'9'))
        { 
          if(ch=='-')
            { 
              f=-f;
            }
          ch=getchar();
        }
      while((ch>='0')&&(ch<='9'))
        { 
          x=x*10+ch-'0';
          ch=getchar();
        }
      return x*f;
    }
    
    const int maxn=65536;
    
    int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10];
    
    int getprime()
    { 
      p[1]=mu[1]=1;
      for(int i=2; i<=maxn; ++i)
        { 
          if(!p[i])
            { 
              prime[++cnt]=i;
              mu[i]=-1;
            }
          for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)
            { 
              int x=i*prime[j];
              p[x]=1;
              if(i%prime[j]==0)
                { 
                  mu[x]=0;
                  break;
                }
              mu[x]=-mu[i];
            }
        }
      return 0;
    }
    
    long long calc(int n,int d)
    { 
      long long ans=0;
      for(int i=1; i<=d; ++i)
        { 
          int t=n/i;
          for(int l=i+1,r; (l<(i<<1))&&(l<=t); l=r+1)
            { 
              r=std::min((i<<1)-1,t/(t/l));
              ans+=1ll*(r-l+1)*(t/l);
            }
        }
      return ans;
    }
    
    int n,s;
    
    int main()
    { 
      getprime();
      n=read();
      s=sqrt(n);
      long long ans=0;
      for(int i=1; i<=s; ++i)
        { 
          ans+=mu[i]*calc(n/i/i,s/i);
        }
      printf("%lld\n",ans);
      return 0;
    }

转载于:https://www.cnblogs.com/Canopus-wym/p/10376084.html

[https_lydsy.com_JudgeOnline_problem.php_id_2671]: https://lydsy.com/JudgeOnline/problem.php?id=2671