What happens when the order is greater than 1e9? Wouldn't a permutation with cycle lengths equal to first N primes easily exceed order 1e9? For example lcm ( 3, 5, 7.. 29 )

This works correct even with 1000 numbers. (What else compilator wants? ))

#include <stdio.h>
int nod(int a, int b){
    while (a != 0 && b != 0){
        if (a > b)
            a = a % b;
        else
            b = b % a;
    }
    return a+b;
}
int main(){
    int size;
    int result = 1;
    scanf_s("%i", &size);
    int arr[1001];
    bool mask[1001];
    for (int i = 0; i < size; ++i)
        scanf_s("%i", &arr[i]);
    for (int i = 0; i < size; ++i){
        int k = 1, temp = arr[i];
        while (temp != i + 1){
            temp = arr[temp - 1];
            ++k;
        }
        if (mask[k] != false){
            mask[k] = false;
        result =result/nod(result,k) * k;

        }
    }
    printf("%i", result);
}

If you don't feel like reviewing my code at least give me some tests please.
So... um... I think my code should work... I tested it along with an accepted program... and it worked fine... Here's the code:

#define DM 1001
#include <bitset>
#include <iostream>
#include <set>
using namespace std;

bitset <DM> bs;
bool verif;
int n, c, lg[DM], mp[DM];
long long v;
set <int> s;

void recursiv (int a)
{
    bs[a] = 1;
    ++v;
    if (s.find(mp[a]) != s.end())
        return;
    s.insert(a);
    recursiv(mp[a]);
}

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> mp[i];
        if (mp[i] == i)
            bs[i] = 1;
    }
    for (int i = 1; i <= n; ++i)
        if (!bs[i])
        {
            recursiv(i);
            s.clear();
            lg[++c] = v;
            v = 0;
        }
    for (v = lg[1]; !verif; ++v)
    {
        verif = 1;
        for (int i = 1; i <= c; ++i)
            if (v%lg[i] != 0)
                verif = 0, i = c + 1;
    }
    cout << v - 1;
    return 0;
}

Hi
I try to solve this task by computing cycle for i in [1..n] (k : P^k(i) = i) and multiplying all k[i] (not forgetting about if k[j] > k[i] and k[j] % k[i] == 0 then k[i] = 1)
And i got the WA #7. Where is my mistake?
Sorry for my poor english.

It does not use long long. It does not use any mathematical algorithm like GCD.
See if you can find it.

New test was added, 1158 AC solutions failed.

Here are some hints
1)Try to find the number of steps for every number to the final position and put it into a array
2)then try to find the least common multiple off all elements from the resulted array
let's consider an exemple 1 2 3 4 (the input is 4      )
                          4 2 1 3               4 2 1 3
int var = a[1] (in this example a[1] = 4 considering the array start from 1).
while(var != i) (i = 1 the first index of the array)
{
     var = a[var]; ((var)4 = a[4], var = 3, than 3 = var[3], var = 1(found the last position)
     k++; (is the number of steps that take to bring to last position)
}
lets make the array of k
x[i] = k;  than k = 0;
i++;
this array will look like i <- 1,n (3 1 3 3)
than just find the least common multiple for all elements that is 3
input                output
4                    3
4 2 1 3
and now the sample
5
4 1 5 2 3
the count arraw will look like
x[] = (3 3 2 3 2)
and the least common multiple is 6
explenation
a[1] = 4
var = a[1] = 4(k = 1)
var = a[var](4 = a[4])(k = 2) var = 2 after 2 = a[2] = 1(k = 3) (finish)
first k = 3 steps
x[1] = 3
after
i++;
var = a[2] ( var = 1 ) after 1 = a[1] (var = 4) after (4 = a[4] = 2 = i) finish
k = 3
and so on until the last element
I hope this will help (i'm not very good at expanation but i try).

I always WA at TEST9,who can give me a test like test9 ? other test in discuss were all used.It's right.

In this test n == 1.

1000
667 928 631 381 248 770 680 540 823 725 404 705 505 375 625 430 372 737 112 614 717 666 603 291 584 202 200 109 443 10 188 917 275 560 766 419 41 153 273 356 771 761 814 319 509 215 148 995 75 107 678 428 484 892 469 312 412 303 830 251 976 594 98 658 25 702 832 652 559 759 144 668 561 571 853 522 546 295 831 268 490 73 946 916 227 873 77 913 416 364 329 554 446 592 235 392 367 882 175 885 973 167 337 958 637 327 357 61 674 163 220 413 297 753 836 88 259 648 696 74 566 197 486 845 299 300 187 134 352 5 833 547 701 587 809 927 99 411 994 609 639 152 116 962 570 691 230 340 118 616 850 682 154 872 709 613 982 552 980 33 944 802 343 380 675 612 267 71 242 605 474 417 348 437 538 211 442 393 640 868 671 241 253 272 38 852 173 120 14 395 96 679 149 589 294 621 351 626 813 420 768 683 706 165 947 783 289 735 854 160 451 213 550 378 305 697 137 581 775 212 740 508 258 1 710 429 426 598 354 754 17 915 948 31 739 309 476 111 838 792 951 410 969 764 78 339 341 84 829 596 280 145 844 543 448 837 214 672 627 500 905 551 176 353 30 366 815 745 502 582 189 983 760 890 580 563 169 805 229 912 179 935 769 586 13 981 314 865 481 487 974 532 860 910 418 930 288 434 369 541 221 433 857 649 835 979 533 48 362 940 345 302 475 953 317 855 565 839 727 530 266 907 901 945 608 998 461 923 818 539 39 900 588 62 483 820 786 102 964 542 318 282 473 308 604 886 315 734 464 756 789 126 68 665 231 494 804 119 445 224 713 772 66 992 479 388 724 385 264 114 478 977 403 847 324 685 758 904 389 520 85 993 301 191 677 777 866 453 535 937 622 363 217 590 252 553 822 279 690 906 472 731 870 784 793 569 782 263 743 170 110 796 306 529 693 887 523 755 715 3 250 602 332 182 512 311 205 57 1000 69 238 81 978 244 370 526 328 97 390 827 781 344 359 564 787 960 491 55 963 192 257 617 595 748 401 736 795 365 729 936 778 201 773 514 142 576 698 384 262 210 889 548 942 812 50 908 511 628 56 573 488 27 260 555 24 572 350 274 255 91 694 136 382 746 646 423 440 988 2 601 233 848 583 618 921 452 669 578 131 7 108 534 660 515 689 774 485 858 94 498 60 207 521 226 629 400 208 699 32 856 800 459 714 965 984 425 493 810 765 379 64 204 158 828 52 304 199 482 859 558 877 692 501 408 139 103 767 638 16 162 791 726 47 891 457 455 184 862 700 851 347 799 506 990 711 664 450 100 661 67 599 579 688 326 895 624 466 316 398 338 790 287 536 585 222 879 914 610 383 397 278 26 721 655 132 180 975 159 218 147 528 174 635 878 518 83 124 763 181 470 641 310 999 70 190 156 458 254 798 471 406 298 130 376 166 196 776 93 966 647 611 247 28 883 728 44 72 919 35 281 9 104 203 82 918 127 414 49 157 177 321 884 650 245 313 415 391 893 642 797 45 780 438 125 556 531 961 285 95 952 607 503 396 377 284 987 794 811 863 293 902 788 349 898 42 876 950 223 23 630 46 989 499 986 325 468 65 779 663 296 676 386 821 185 239 591 517 54 113 619 707 463 277 920 525 194 954 971 557 361 449 322 575 402 355 751 86 636 424 881 941 926 117 593 722 225 527 719 292 894 135 720 704 968 524 623 807 744 562 387 141 198 373 985 234 806 826 330 943 121 43 684 427 513 922 336 63 331 36 320 22 444 219 195 441 465 742 178 620 151 651 209 37 150 840 496 342 4 903 869 841 489 76 733 750 161 477 816 172 747 431 51 577 819 129 409 29 934 265 600 897 849 89 435 959 597 53 206 480 932 864 549 105 168 997 171 128 243 460 834 138 824 246 58 106 15 545 8 216 861 909 261 454 803 825 421 730 92 394 695 537 183 996 11 867 358 333 899 186 164 6 880 122 456 933 732 645 12 687 467 495 87 193 633 59 567 228 256 896 712 232 957 80 643 817 970 115 568 752 924 504 749 938 606 874 249 654 405 447 632 270 656 574 681 723 659 40 432 236 335 741 101 644 929 967 371 657 703 762 323 360 931 615 991 79 911 686 271 155 738 888 846 34 123 519 875 368 670 462 497 842 716 949 290 21 283 20 757 925 653 143 346 240 662 18 276 516 871 133 972 544 407 510 399 785 307 708 19 237 956 673 334 439 90 146 374 507 436 718 634 422 801 140 808 269 286 843 492 939 955

The answer is 805627284

My algo works with 255 Kb memory and 1ms. what can I improve in code to get ~120 KB, as in best results?

[code deleted]

Edited by moderator 04.12.2019 20:44

var
  a: array[1..1000, 1..10001] of integer; c, d, e: integer;

label 1;
begin
  randomize;
  d := 1;
  Readln(c);
  for e := 1 to c do read(a[e, 10001]) {a[e,1002]:=random(c-1)+1};
  for e := 1 to c do a[e, 1] := e;
  1: inc(d);
  //for e:= 1 to c do write (a[e,1001],' ');
  for e := 1 to c do a[a[e, 10001], d] := a[e, d - 1];
  for e := 1 to c do if a[e, d] <> a[e, 1] then goto 1;
  writeln(d - 1);
end.

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

In testing my code .. it gets stuck in toggling between 41325 and 24315...and ends in infinite loop.

Can anyone help me with what I might be doing wrong ?

Thank you!
In this forum I knew how solve this task!

We must find lengths of pathes for every element of permutation and count their LCM.

Don't forget about Int64 in Pascal and long long in C++.

Here is my AC solution:

[code deleted]

Edited by author 15.08.2005 07:46

Edited by moderator 04.12.2019 20:48

the solution is achieved using LCM (MCM in Spanish) and long long to express the result

This is my program

[code deleted]

Edited by moderator 04.12.2019 20:51

#include <cstdio>
using namespace std;
 int main()
{
     int const Q=1001;
     long long unsigned k = 0,i,n,a=0;
    scanf("%llu",&n);
    long long unsigned mas1[Q];
    long long unsigned mas2[Q];
    for(i = 1;i<=n;i++)
    { scanf("%llu",&mas1[i]);
     mas2[i] = mas1[i];
    }
    for(;;)
   {
       for(i = 1;i<=n;i++)
     {
         if (i == mas2[i]){ k++;}
         mas2[i] = mas1[mas2[i]];
     }
      a++;
     if ( k == n) { break;} else {k = 0;}
   }
    printf("%llu\n",a);
   return 0;
}

#include <cstdio>


using namespace std;

/*
 *
 */
 int main()
{


    long long k = 0;
     long long i;
     long long unsigned n;
    scanf("%llu",&n);
    long long unsigned mas1[1000];
    long long unsigned mas2[1000];
    for(i = 1;i<=n;i+=1)
    { scanf("%llu",&mas1[i]);
     mas2[i] = mas1[i];
    }
    long long unsigned a = 0;
    long long s = 0;
    long long m = 0;
   do
   {
       for(long long j = 1;j<=n;j+=1)
     {
         if (j == mas2[j]){ k+=1;}
     }
    for(i = 1;i<=n;i+=1)
    {
        s = mas2[i];
        mas2[i] = mas1[mas2[i]];
    }
     if ( k == n) { m=1;} else {k = 0;}
    a+=1;
   } while (m!=1);
    printf("%llu\n",a);
   return 0;
}

HELP!!!






#include <iostream>

using namespace std;

int main()
{
    int const N=1024;
    int n, a[N], b[N], P=1;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }


    for(;;)
    {
        int s=0;
        for(int i=0;i<n;i++)
            if(a[i]==i+1)
                s++;

        if(s==n)
            break;

        else
        {
            P++;
            for(int j=0;j<n;j++)
                a[j]=b[a[j]-1];
        }
    }

    cout<<P<<endl;



    return 0;
}