結果

問題 No.1653 Squarefree
ユーザー merlin
提出日時 2022-05-03 06:12:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,540 ms / 2,000 ms
コード長 1,768 bytes
コンパイル時間 1,434 ms
コンパイル使用メモリ 171,816 KB
実行使用メモリ 90,112 KB
最終ジャッジ日時 2024-07-02 10:20:03
合計ジャッジ時間 29,384 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=17705360;
bool p[N]; int mob[N];
void mobius(int n)
{
int i,j;
for(i=0;i<=n;i++) {p[i]=false; mob[i]=1;}
for(i=2;i<=n;i++)
if(!p[i])
{
mob[i]=-1;
for(j=2;j<=n/i;j++)
{
p[i*j]=true;
mob[i*j]*=-1;
}
ll sq=1LL*i*i;
for(j=1;j<=n/sq;j++)
mob[j*i*i]=0;
}
}
int maxpower(ll n,int p)
{
if(n==0) return 1;
int l=1,r=(int)1e9,m,ans,i;
if(p==5) r=3190;
ans=r;
while(l<=r)
{
m=(l+r)>>1;
ll v=1;
for(i=0;i<p;i++) v*=m;
if(v<=n)
{
ans=m;
l=m+1;
}
else r=m-1;
}
return ans;
}
//https://smsxgz.github.io/post/pe/counting_square_free_numbers/
int squarefree(ll n,int imax,int d)
{
if(d==0) return 0;
vector<int> mxi;
int sum=0,i;
for(i=imax-1;i>0;i--)
{
int cur=1;
int root=maxpower(n/i,2),sqd=maxpower(root,2),j;
for(j=1;j<=root/(sqd+1);j++) cur-=(root/j-root/(j+1))*mob[j];
for(j=2;j<=sqd;j++)
if(root/j<=d) cur-=mob[root/j];
else cur-=mxi[imax-j*j*i-1];
mxi.push_back(cur);
sum+=cur;
}
return sum-(imax-1)*mob[d];
}
int main()
{
ll a,b;
cin>>a>>b;
a--;
int imax=maxpower(b,5),ima=maxpower(a,5);
int d=maxpower(b/imax,2),d2=maxpower(a/ima,2);
int dm=max(d,d2);
mobius(dm);
ll s1=0,s2=0; int i;
mob[0]=0;
for(i=1;i<=dm;i++)
{
if(i<=d) s1+=(b/(1LL*i*i))*mob[i];
if(i<=d2) s2+=(a/(1LL*i*i))*mob[i];
mob[i]+=mob[i-1];
}
s1+=squarefree(b,imax,d); s2+=squarefree(a,ima,d2);
cout<<(s1-s2)<<"\n";
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0