2 条题解

  • 0
    @ 2025-10-8 17:05:16
    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    const int N=1e5;
    int pr, p[N+10];LL mu[N+10],F[N+10];bool v[N+10];
    void init()
    {
        memset(v, 0, sizeof(v));
    	pr=0;mu[0]=0;mu[1]=1;
        for(int i=2;i<=N;i++)
    	{
            if(!v[i]) p[++pr]=i, mu[i]=-1; 
            for(int j=1;j<=pr&&p[j]*i<=N;j++)
    		{
                v[i*p[j]]=true;
                if(i%p[j]==0) {mu[i*p[j]]=0; break;}
                mu[i*p[j]]=-mu[i];
            }
        }
        F[0]=0;
    	for(int i=1;i<=N;i++)for(int j=i;j<=N;j+=i)
    		F[j]+=mu[j/i]*i;
    	for(int i=1;i<=N;i++)F[i]+=F[i-1];
    }
    LL calc(LL n,LL m)
    {
    	LL ans=0;
        for(LL l=1,r;l<=n;l=r+1)
    	{
            r=min(n/(n/l),m/(m/l));
            ans+=(F[r]-F[l-1])*(n/l)*(m/l);
        }
        return 2*ans-n*m;
    }
    int main()
    {
    	init();
        LL n,m;scanf("%lld%lld",&n,&m);if(n>m)swap(n,m);
        printf("%lld\n",calc(n,m)); 
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:05:05
      #include<bits/stdc++.h>
      #define LL long long
      using namespace std;
      const int N=1e5;
      int pr, p[N+10];LL mu[N+10],F[N+10];bool v[N+10];
      void init()
      {
          memset(v, 0, sizeof(v));
      	pr=0;mu[0]=0;mu[1]=1;
          for(int i=2;i<=N;i++)
      	{
              if(!v[i]) p[++pr]=i, mu[i]=-1; 
              for(int j=1;j<=pr&&p[j]*i<=N;j++)
      		{
                  v[i*p[j]]=True;
                  if(i%p[j]==0) {mu[i*p[j]]=0; break;}
                  mu[i*p[j]]=-mu[i];
              }
          }
          F[0]=0;
      	for(int i=1;i<=N;i++)for(int j=i;j<=N;j+=i)
      		F[j]+=mu[j/i]*i;
      	for(int i=1;i<=N;i++)F[i]+=F[i-1];
      }
      LL calc(LL n,LL m)
      {
      	LL ans=0;
          for(LL l=1,r;l<=n;l=r+1)
      	{
              r=min(n/(n/l),m/(m/l));
              ans+=(F[r]-F[l-1])*(n/l)*(m/l);
          }
          return 2*ans-n*m;
      }
      int main()
      {
      	init();
          LL n,m;scanf("%lld%lld",&n,&m);if(n>m)swap(n,m);
          printf("%lld\n",calc(n,m)); 
          return 0;
      }
      • 1

      信息

      ID
      3670
      时间
      1000ms
      内存
      128MiB
      难度
      9
      标签
      递交数
      7
      已通过
      5
      上传者