Cod sursa(job #138056)

Utilizator mgntMarius B mgnt Data 17 februarie 2008 20:15:28
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
# include <iostream>
# include <fstream>
# include <vector>
# include <set>
# include <algorithm>
using namespace std;

int
main () {
  int n ; // 1 <= n <= 1.000.000
  ifstream sin ( "fractii.in" ) ;
  sin >> n ;
  sin . close ( ) ;
  vector < int > p ;
  vector < int > q ;
  p . resize  ( 1 + n ) ;
  q . resize  ( 1 + n ) ;
  int i , j , k , t , s;
  for ( i = 1 ; i <= n ; ++ i ) {
    p [ i ] = 0 ;
  }
  p [ 1 ] = 1 ; q [ 1 ] = 1 ; i = 2 ; k = 1;
  while ( i < n ) {
    make_heap ( & q [ 1 ] , & q [ 1 + k ] ) ;
    sort_heap ( & q [ 1 ] , & q [ 1 + k ] ) ;
    j = 1 ;
    s = k ;
    while ( j <= k ) {
      t = i * q [ j ] ;
      if ( n < t ) {
        j = 1 + n ;
      } else {
        if ( 0 == p [ t ] ) {
          ++ s ;
          q [ s ] = t ;
          p [ t ] = i ;
        }
      }
      ++ j ;
    }
    j = k + 1;
    k = s;
    while ( j <= k ) {
      t = i * q [ j ] ;
      if ( n < t ) {
        j = 1 + n ;
      } else {
        ++ k ;
        q [ k ] = t ;
        p [ t ] = i ;
      }
      ++ j ;
    }
    i = i + 1;
    while ( ( i < n ) && ( 0 != p [ i ] ) ) {
      i = i + 1;
    }
  }
  s = 1 ;
  for ( i = 2 ; i <= n ; i ++ ) {
    set < int > desc ;
    j = i ;
    t = p [ j ] ;
    while ( 1 != t ) {
      desc . insert ( t ) ;
      j = j / t ;
      t = p [ j ] ;
    }
    j = i ;
    set < int > :: iterator it  = desc . begin () ;
    set < int > :: iterator it_end = desc . end   () ;
    while ( it != it_end ) {
      k = * it  ;
      j = j / k ;
      j = j * ( k - 1 ) ;
      ++ it ;
    }
    s = s + 2 * j ;
  }
  ofstream sout ( "fractii.out" ) ;
  sout << s << endl ;
  sout . close ( ) ;
  return 0 ;
}