CF741A 题解

· · 题解

洛谷题目传送门

CF题目传送门

更好的阅读体验？

题目翻译

在小A的地盘上有许多可爱的妹子。小A的地盘上的所有人被从 1 到 n 编号，每个人都有一个暗恋的对象，第 i 个人暗恋第 crush_{i} 个人。 有一天，小A在宫殿的顶部大声喊着 Owf ，于是一个有趣的游戏在小A的地盘上开始了。

游戏规则如下： 该游戏有许多轮。如果编号为 x 的人想要开始一轮游戏，他会对第 crush_{x} 个人（ x 暗恋的人 ）说 Oww...wwf（有 t 个 w ）。如果 t > 1，第 crush_{x} 个人就会对第 crush_{crush_{x}} 个人（crush_{x}暗恋的人）说 Oww...wwf（有 t - 1 个 w）。直到有人听到 Owf（t = 1）。这个人就是这一轮的 Joon-Joon。不存在同时进行两轮游戏的情况。

为了使游戏更有意思，小M有一个邪恶的计划。他想找到最小的 t（t \geq 1）使得对于每个人 x 当第 x 个人开始的一局游戏使 y 成为了 Joon-Joon，也使得由 y 开始的一局游戏 x 成为 Joon-Joon。请为小M找这个最小的 t。 可能会有自恋的人。

这道题就是输入一个链表，先让你判断链表中的点是否都在某一个环中，让后让你求出所有环的点数的 lcm，对于偶数环在求 lcm 时将该偶数环的点数减半。 很多个人，一次给对应的人打电话。第 t 个人就是第 1 个人的 Joon-Joon。问 t 最小为多少可以让每两个人互为 Joon-Joon。

解题思路

题目翻译太恶心了。这道题就是输入一个链表，先让你判断链表中的点是否都在某一个环中，让后让你求出所有环的点数的 lcm，对于偶数环在求 lcm 时将该偶数环的点数减半。

这样，题目就简单多了。注意开 long long！

AC 代码

#include<cstdio>
typedef long long ll;
ll gcd(ll a, ll b){
    if(!a){
        return b;
    }else if(!b){
        return a;
    }else{
        return gcd(b, a%b);
    }
}
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
ll a[101], vis[101]; 
int main(){
    ll n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    ll ans = 1;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            int Author_AK_IOI = i, Readers_AK_IOI = 0;
            while(!vis[Author_AK_IOI]){
                vis[Author_AK_IOI] = 1;
                Readers_AK_IOI++;
                Author_AK_IOI = a[Author_AK_IOI];
            }
            if(Author_AK_IOI != i){
                puts("-1");
                return 0;
            }
            if(!(Readers_AK_IOI%2)){
                Readers_AK_IOI /= 2;
            }
            ans = lcm(ans, Readers_AK_IOI);
        }
    }
    printf("%lld", ans);
    return 0;
}