trang chủ / đề bài / icpc23_mb_l

Euler

Đề bài

Mô tả

Cho hai số nguyên dương A và B. Hãy tính tổng giá trị hàm phi Euler của B bội số đầu tiên của A, tức là

φ(A)+φ(2A)+φ(3A)+…+φ(B·A).

Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho 998244353.

Hàm phi Euler φ(n) của số nguyên dương n là số lượng số nguyên k thỏa mãn 1≤k≤n và gcd(n,k)=1, trong đó gcd(a,b) là ước chung lớn nhất của a và b.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên A và B (1≤A,B≤5×106).

Dữ liệu ra

In ra một dòng chứa đáp án: tổng giá trị hàm phi Euler của B bội số đầu tiên của A, lấy phần dư khi chia cho 998244353.

Ràng buộc

  • 1≤A,B≤5×106

Ví dụ

Input Output Giải thích
2 4 9 φ(2)+φ(4)+φ(6)+φ(8)=1+2+2+4=9.
1 3 4 φ(1)+φ(2)+φ(3)=1+1+2=4.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0