J - Jumping frog Gym - 101889J(gcd,置换)
题意:R可与走,P不可以走。可以任选起点,每步的长度为k。求问存在多少k,使得你最后可以跳回起点。从i跳一步后会变成(i+k)%n思路:感觉和之前写过的置换很像,也是在环上跳。对于所跳的步长k,如果gcd(n,k)=1,那么实际就是要遍历每一个点,必须得满足所有点都是R。否则的话,最终要跳n∗k/gcd(n,k)/k=n/gcd(n,k)n*k/gcd(n,k)/k=n/gcd(n,k)n∗k/gcd(n,k)/k=n/gcd(n,k)步。这个部分的个数等于n的约数的个数,不会很多。所以我