Problem 745 | Project Euler |

[sx349]

https://pe-cn.github.io/745/

Problem 745 Sum of SquaresFor a positive integer, $n$, define $g(n)$ to be the maximum perfect square that divides $n$.For example, $g(18) = 9$, $g(19) = 1$. Also define$$\displaystyle S(N) = \sum

[shangkelingxiang]

显然是一个min25可以做的问题，没想正解，暴力跑就行了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=(k);i++)
#define per(i,j,k) for(int i=j;i>=(k);i--)
using i64 = long long;
using i128 = __int128;
auto Min26(const i64 n){
  auto f=[&](int P,int c,i64 pc){
    if(c&1)pc/=P;
    return pc;
  };
  const int lim=sqrt(n);
  vector<int>ge(lim+1),le(lim+1);
    #define id(x) ((x<=lim)?le[x]:ge[n/(x)])
  vector<int>pri(1),lpf(lim+1);
  vector<i64>sprik[3];
  vector<i128>g[3];
  vector<i64>li(2*lim+5);
  vector<i128>Fprime(2*lim+5);
  rep(i,0,2)sprik[i].push_back(0),g[i].resize(2*lim+5);
  int tot=0,pcnt=0;
    rep(i,2,lim){
      if(!lpf[i]){
        lpf[i]=++pcnt;
      pri.push_back(i);
      sprik[0].push_back(sprik[0][pcnt-1]+1);
    }
    for(int j=1;j<=lpf[i]&&i*pri[j]<=lim;j++)lpf[i*pri[j]]=j;
  }
  for(i64 i=1,j;i<=n;i=n/j+1){
    j=n/i;
    li[++tot]=j;
    id(j)=tot;
    g[0][tot]=j-1;
  }
  rep(k,1,pcnt){
    i64 o=1ll*pri[k]*pri[k];
    for(int i=1;li[i]>=o;i++){
      int d=id(li[i]/pri[k]);
      g[0][i]-=g[0][d]-sprik[0][k-1];
    }
  }
  rep(i,1,tot)Fprime[i]=g[0][i];
  per(k,pcnt,1){
    i64 o=1ll*pri[k]*pri[k];
    for(int i=1;li[i]>=o;i++){
      i64 lio=li[i]/pri[k],pw=pri[k];
      int c=1;
      while(pw<=lio){
        Fprime[i]+=
          f(pri[k],c,pw)*
            (Fprime[id(li[i]/pw)]-
              sprik[0][k]
            )
          +f(pri[k],c+1,pw*pri[k]);
        pw*=pri[k],c++;
      }
    }
  }
  rep(i,1,tot)Fprime[i]+=1;
  return Fprime[1];
}
signed main(){
  i64 n;
  cin>>n;
  cout<<(int)(Min26(n)%1000000007)<<endl;
}

[shangkelingxiang]

或者统计完全平方因子再枚举贡献

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=(k);i++)
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
void print(i128 n){
  vector<int>a;
  while(n)a.push_back(n%10),n/=10;
  reverse(a.begin(),a.end());
  for(int i:a)cout<<i;
}
i64 Smu2(i64 N){
  int n=sqrt(N);
  vector<bool>v(n+1);
  vector<int>pri,mu(n+1);
  mu[1]=1;
  rep(i,2,n){
    if(!v[i])pri.push_back(i),mu[i]=-1;
    for(int p:pri){
      if(i*p>n)break;
      v[i*p]=1;
      if(i%p==0)break;
      mu[i*p]=-mu[i];
    }
  }
  i64 ans=0;
  rep(i,1,n)ans+=N/i/i*mu[i];
  return ans;
}
signed main(){
  i128 ans=0;
  const i64 n=1e14;
  const int m=1e7;
  rep(i,1,m)ans+=(i128)i*i*Smu2(n/i/i);
  print(ans);
}