fork download
copy 
  1. //Codechef July challenge
  2.  
  3. #include<cstdio>
  4. #include<vector>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define MOD 1000000007
  9. #define MAX 1000000
  10. using namespace std;
  11.  
  12. vector<int>graph[100000+7];
  13. vector<int>mark(100000+7);
  14. int n;
  15.  
  16.  
  17. vector<bool>isprime(MAX+5,false);
  18.  
  19. vector<int>prime;
  20.  
  21. void sieve()
  22. {
  23.     isprime[0]=isprime[1]=true;
  24.     for(int i=2;i<=sqrt(MAX);i++)
  25.     {
  26.         if(isprime[i]==false)
  27.         {
  28.             for(int j=2;i*j<=MAX;j++)
  29.                 isprime[i*j]=true;
  30.         }
  31.     }
  32.     for(int i=2;i<=MAX;i++)
  33.         if(isprime[i]==false)
  34.             prime.push_back(i);
  35. }
  36.  
  37. void input()
  38. {
  39.     int num;
  40.     scanf("%d",&n);
  41.     for(int i=1;i<=n;i++)
  42.     {
  43.         scanf("%d",&num);
  44.         graph[i].push_back(num);
  45.         graph[num].push_back(i);
  46.         mark[i]=0;
  47.     }
  48. }
  49.  
  50. int bfs(int s)
  51. {
  52.     queue<int>q;
  53.     q.push(s);
  54.     int count=1;
  55.     mark[s]=1;
  56.     while(!q.empty())
  57.     {
  58.         int nw=q.front();
  59.         q.pop();
  60.         for(int i=0;i<graph[nw].size();i++)
  61.         {
  62.             if(mark[graph[nw][i]]==0)
  63.             {
  64.                 mark[graph[nw][i]]=1;
  65.                 q.push(graph[nw][i]);
  66.                 count++;
  67.             }
  68.         }
  69.     }
  70.     return count;
  71. }
  72.  
  73. int main()
  74. {
  75.     sieve();
  76.     int t;
  77.     scanf("%d",&t);
  78.     while(t--)
  79.     {
  80.         vector<int>keep;
  81.         input();
  82.         for(int i=1;i<=n;i++)
  83.         {
  84.             if(mark[i]==0)
  85.             {
  86.                 keep.push_back(bfs(i));
  87.             }
  88.         } 
  89.         sort(keep.begin(),keep.end());
  90.         vector<int>L(1000000+9);
  91.         int max_p=0;
  92.         for(int i=0;i<keep.size();i++)
  93.         {
  94.             int j=0;
  95.             int count=0;
  96.             while(keep[i]!=0 && j<prime.size())
  97.             {
  98.                 if(keep[i]%prime[j]!=0)
  99.                 {
  100.                     L[prime[j]] =max(L[prime[j]] ,count);
  101.                     count=0;
  102.                     j++;
  103.                 }
  104.                 else
  105.                 {
  106.                     keep[i]/=prime[j];
  107.                     max_p=max(max_p,prime[j]);
  108.                     count++;
  109.                 }
  110.             }
  111.         }
  112.         long long ans=1;
  113.         for(int i=0;i<prime.size();i++)
  114.         { 
  115.             for(int j=1;j<=L[prime[i]];j++)
  116.             {
  117.                     ans*=prime[i];
  118.                     if(ans>MOD)
  119.                         ans%=MOD;
  120.             }
  121.         }
  122.         printf("%lld\n",ans);
  123.     }
  124.     return 0;
  125. }
  126.  
Time limit exceeded #stdin #stdout 5s 9544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/06On7q
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!