fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 1e5 ;
  17. #define debug 0
  18. #define oo (ll)(1e18)
  19.  
  20. int a[maxn+3];
  21.  
  22. vector < int > l[maxn + 3 ] ;
  23. int f[maxn +3];
  24. int find_root ( int u ) {
  25.  
  26. 	return ( f[u] < 0 ) ? u : f[u] = find_root ( f[u]) ;
  27.  
  28. }
  29. void unit ( int x , int y ) {
  30. 	x = find_root ( x ) ;
  31. 	y = find_root ( y ) ;
  32. 	if ( x == y ) return ;
  33. 	if ( f[x] > f[y] ) swap ( x , y );
  34. 	f[x] += f[y] ;
  35. 	f[y] = x ;
  36. 	return ;
  37. 	#define toi_dep_trai_qua  true 
  38. 	assert ( toi_dep_trai_qua );
  39. }
  40. void input(){
  41. }
  42. #define name "TASK" 
  43. int main(){
  44.     fast 
  45.     if(fopen(name".INP","r")) {
  46.         freopen (name".INP","r",stdin);
  47.         freopen (name".OUT","w",stdout);
  48.     }
  49.     int n ; cin >> n ;
  50.     FOR ( i , 1 , n ) cin  >> a[i] ;
  51.     FOR ( i , 1 , n ) {
  52.     	int c = a[i] ;
  53.     	for ( int w = 1 ; w * w <= c ; w ++ ) {
  54.     		if ( c % w == 0 ) {
  55.     			l[w].pb ( i ) ;
  56.     			if ( c / w != w ) l[c/w].pb(i) ;
  57.     		}
  58.     	}
  59.     }
  60.     memset ( f , -1 , sizeof ( f)) ;
  61.     static const int MAXX = 1e5 ;
  62.     #define FORD(i,a,b) for (ll i = (a) ; i >= (b) ; i -- ) 
  63.     ll res = 0 ;
  64.     FORD( w , MAXX , 1 ) {
  65.     	if ( l[w].size() == 0 ) continue ;
  66.     	rep ( i , 1 , (int)l[w].size()){
  67.     		if (find_root(l[w][0]) != find_root (l[w][i]) ){
  68.     			res += w ;
  69.  
  70.     			unit ( l[w][0] , l[w][i]) ;
  71.  
  72.     		}
  73.     	}
  74.     }
  75.     ll d = 123456ll * (n-1) ;
  76.     cout << d - res ; 
  77.  
  78.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  79.     return(0) ;
  80. }
Success #stdin #stdout #stderr 0.01s 6444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-44332193432640
stderr
copy 
TIME: = 0.005296
https://ideone.com/uHj4Vu
language:
C++14 (gcc 8.3)
created:
21 hours 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!