#1295D. Same GCDs
给定正整数 $a$，$m$（$a<m$）。计算符合条件的 $x\in[0,m)$ 的个数，使得 $\text{gcd}(a,m)=\text{gcd}(a+x,m)$。
$a\le 1e10,m\le 1e10$
如果题目中定义一种等价关系，满足等价关系的元素被看成同一类，只统计一次；这样的问题称为等价类计数问题。一般的等价类计数问题可以用 Burnside 引理或 Pólya定理解决。
刚复习了一遍 qwq 我当时写得真好
tth37
Think twice, Code once.
Jiangsu, China
Posts
120
Categories
21
Tags
82
WTF
题解 / 计蒜客
Update your browser to view this website correctly. Update my browser now
×