Pagini recente » Cod sursa (job #283604) | Cod sursa (job #169056) | Cod sursa (job #527464) | Cod sursa (job #1171856) | Cod sursa (job #138056)
Cod sursa(job #138056)
# 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 ;
}