1.送分题，\(O(n)\)处理前后缀，枚举断点,或者\(nlogn\)线段树暴力即可
2.根据\(a_i \times k \equiv x\pmod{n}\),导出\(gcd(a_i,n)|x\),我们枚举d|n,如果\(gcd(a_i,n)|d,那么所有的满足gcd(x,n)=d,的x都能被走到\)
因为,d为x的约数,\(gcd(a_i,n)\)为d的约数,所以\(gcd(a_i,n)|x\).
原文：https://www.cnblogs.com/ARTlover/p/9784403.html