Cod sursa(job #138104)

Utilizator mgntMarius B mgnt Data 17 februarie 2008 21:06:22
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 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 > s ;
  s . resize  ( 1 + n ) ;
  int i , j , k ;
  for ( i = 1 ; i <= n ; ++ i ) {
    s [ i ] = i ;
  }
  i = 2 ;
  while ( i <= n ) {
    k = i - 1 ;
    for ( j = i ; j <= n ; j += i ) {
      s [ j ] = s [ j ] / i ;
      s [ j ] = s [ j ] * k ;
    }
    ++ i ;
    while ( ( i <= n ) && ( i != s [ i ] ) ) {
      ++ i ;
    }
  }
  long long int ans = s [ 1 ] ;
  for ( i = 2 ; i <= n ; i ++ ) {
    ans += 2 * s [ i ] ;
  }
  ofstream sout ( "fractii.out" ) ;
  sout << ans << endl ;
  sout . close ( ) ;
  return 0 ;
}