kkk, i figured out about the LCMs pretty much myself, but i just keep getting WAs on tests like 4 or 3 and that's sooo embarassing
<code>
#include <stdio.h>
#include <cmath>
#include <set>

using namespace std;

long long gcd(long long a, long long b) {
    return !b ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return (a / gcd(a,b) * b);
}

int main()
{

    int n;

    scanf("%d", &n);

    set<int> ds; // a usual stl set which stores the distaces of all elements
    int tmp;
    for(int i=1;i<n+1;i++) {
        scanf("%d", &tmp);
        ds.insert(abs(i-tmp));
    }

    long long res;
    if(ds.size() == 1 && ds.count(0)) res = 1;
    else {
        if(ds.count(0)) ds.erase(ds.find(0));
        res = 1;
        for (set<int>::iterator it = ds.begin(); it != ds.end(); ++it) {
            res = lcm(res,*it);
        }
    }

    printf("%lld", res);

}
</code>
And the worst thing is I just can't think of a straightforward test for which that gives a wrong answer.
5  4 1 5 2 3 => 6
1  1 => 1
5  1 2 3 4 5 => 1
6  6 5 3 4 2 1 => 15
didn't check for ns like 100 and i don't think that's the problem. also i don't think the problem is about malformed longlong operation, cause if i replace that with ints the WAs are all the same.
would really like if someone helped me 'bout that ((


Edited by author 28.11.2011 19:38

"Every problem has a simple, fast and wrong solution."
- that one is soooo right :D

i mean, i came up with the distances of the items, but those actually should be the lengths of cycles ))
it was like 4 1 5 2 3 => 3 2 1 2 2
but should be like 4 1 5 2 3 => 3 3 2 3 2
 - and it's really straightforward to figure out how it works :D
the worst thing about my initial solution is that it worked in some trivial cases :)

now i made something like that:
[code deleted]
and finally got AC after 23 WAs :) so happy 'bout that


Edited by moderator 04.12.2019 20:47

Look out for left over debug prints!   I was tearing my hair out over WAs after I figured out doing the LCM of all the unique cycle counts and was convinced the approach was correct, and I was right!   But one left over debug print messed me up until I finally saw it.