結果

問題 No.1653 Squarefree
ユーザー 👑 Nachia
提出日時 2024-01-28 17:50:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,239 bytes
コンパイル時間 647 ms
コンパイル使用メモリ 55,164 KB
最終ジャッジ日時 2025-02-19 00:34:01
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:112:26: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  112 |     long long L, R; scanf("%lld%lld", &L, &R);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

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

#include <vector>
#include <cassert>
namespace nachia{
namespace internal{
// mod 2^64
constexpr unsigned long long PowerOfULongLong(unsigned long long a, unsigned long long i){
unsigned long long res = 1;
while(i){ if(i&1){ res *= a; } i /= 2; a *= a; }
return res;
}
}
unsigned long long FloorOfKthRoot(unsigned long long real, unsigned long long k){
using u64 = unsigned long long;
assert(k != 0);
if(real <= 1) return real;
if(k >= 64) return 1;
if(k == 1) return real;
struct Precalc{
// a^i <= x
static constexpr bool lesseq(u64 a, int i, u64 x) {
if (a == 0) return true;
for(int j=0; j<i; j++) x /= a;
return x >= 1;
}
unsigned long long BORDER[64];
constexpr Precalc() : BORDER() {
for (int idx = 2; idx <= 63; idx++) {
u64 l = 0, r = 1ull << 33;
while (l + 1 < r) {
u64 m = (l + r) / 2;
if (lesseq(m, idx, ~0ull)) l = m;
else r = m;
}
BORDER[idx] = r;
}
};
};
constexpr Precalc precalc;
u64 l = 0, r = precalc.BORDER[k];
if(real < r) r = real;
while (l + 1 < r) {
u64 m = (l + r) / 2;
if(internal::PowerOfULongLong(m, k) <= real) l = m;
else r = m;
}
return l;
}
unsigned long long CeilOfKthRoot(unsigned long long real, unsigned long long k){
if(real <= 1) return real;
if(k >= 64) return 2;
if(k == 1) return real;
unsigned long long x = FloorOfKthRoot(real, k);
if(internal::PowerOfULongLong(x, k) != real) x++;
return x;
}
} // namespace nachia
namespace nachia{
long long CountSquarefree(long long n){
using i64 = long long;
i64 s = 0;
auto getMobius = [&](i64 n){
std::vector<bool> sieve(n+1, true);
std::vector<signed char> mu(n+1, 1);
for(i64 i=2; i<=n; i++) if(sieve[i]){
mu[i] = -1;
for(i64 j=i*i; j<=n; j+=i) sieve[j] = false;
for(i64 j=i*2; j<=n; j+=i) mu[j] = -mu[j];
for(i64 j=i*i; j<=n; j+=i*i) mu[j] = 0;
}
return mu;
};
if(n <= 4000){
auto mu = getMobius(n+1);
for(i64 i=1; i*i<=n; i++) s += n/(i*i) * mu[i];
return s;
}
i64 I = nachia::FloorOfKthRoot(n, 5) * 2;
i64 D = nachia::FloorOfKthRoot(n/(I+1), 2);
auto mu = getMobius(D+1);
std::vector<int> Mf(D+1);
for(i64 i=1; i<=D; i++) Mf[i] = Mf[i-1] + mu[i];
std::vector<i64> Md(I+1);
for(i64 i=I; i>=1; i--){
i64 m = 1;
i64 x = nachia::FloorOfKthRoot(n/i, 2);
i64 Dx = nachia::FloorOfKthRoot(x, 2);
i64 Rx = x / (Dx+1);
i64 r = 2;
for( ; i*r*r<=I; r++) m -= Md[i*r*r];
for( ; r<=Rx; r++) m -= Mf[x/r];
for(i64 d=1; d<=Dx; d++) m -= mu[d] * (x/d - Rx);
Md[i] = m; s += m;
}
for(i64 i=1; i<=D; i++) s += mu[i] * (n/(i*i) - I);
return s;
}
} // namespace nachia
#include <cstdio>
int main(){
long long L, R; scanf("%lld%lld", &L, &R);
long long ans = nachia::CountSquarefree(R) - nachia::CountSquarefree(L-1);
printf("%lld\n", ans);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0