网站首页
编程语言
数据库
系统相关
其他分享
编程问答
1673
2024-06-07
timus 1673 & phi & 反phi
题意:给定\(k\),求一个最小的\(n\)使得有恰好\(k\)个\(i\in[1,n]\),满足对于所有\(j\in[1,n]\),都有\(x\)满足\(ix=j\modn\)并且\(ix\len^2\)。里面所有数都是正整数。Sol:我们考虑\(\gcd(x,n)>1\)的\(x\)。因为\(\gcd(x,n)>1\),所以\(\operatorname{lcm}(x,n