題意:
(from luckycat)
解 法:
跟 http://mobcs.blogspot.tw/2015/04/uva-10179-irreducable-basic-fractions.html 差不多，
只是因為題目的要求 當 n = 1 的時候，答案是 0。
TAG: Math
注意:
程式碼:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Tittle: 10299 - Relatives | |
| * Author: Cheng-Shih, Wong | |
| * Date: 2015/06/11 | |
| */ | |
| // include files | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| // definitions | |
| #define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i ) | |
| #define clr(x,v) memset( x, v, sizeof(x) ) | |
| #define N 31623 | |
| typedef vector<int> VI; | |
| // declarations | |
| bool isp[N+10]; | |
| VI pm; | |
| int n; | |
| int cnt; | |
| VI fact; | |
| // functions | |
| void init( void ) | |
| { | |
| clr( isp, true ); | |
| isp[0] = isp[1] = false; | |
| pm.clear(); | |
| FOR( i, 2, N ) if( isp[i] ) { | |
| pm.push_back(i); | |
| for( int j=i*i; j<=N; j+=i ) | |
| isp[j] = false; | |
| } | |
| } | |
| void calc( int l, int rem, int val, bool plus ) | |
| { | |
| if( l>=fact.size() || rem==0 ) { | |
| if( rem ) return; | |
| if( plus ) cnt += n/val; | |
| else cnt -= n/val; | |
| return; | |
| } | |
| calc( l+1, rem-1, val*fact[l], plus ); | |
| calc( l+1, rem, val, plus ); | |
| } | |
| void solve( void ) | |
| { | |
| if( n==1 ) { | |
| puts("0"); | |
| return; | |
| } | |
| fact.clear(); | |
| int k = n; | |
| for( int v : pm ) { | |
| if( v*v > k ) break; | |
| if( (k%v)==0 ) { | |
| fact.push_back(v); | |
| while( (k%v)==0 ) k/=v; | |
| } | |
| } | |
| if( k!=1 ) fact.push_back(k); | |
| cnt = 0; | |
| FOR( i, 1, fact.size() ) | |
| calc( 0, i, 1, (i&1) ); | |
| printf( "%d\n", n-cnt ); | |
| } | |
| // main function | |
| int main( void ) | |
| { | |
| init(); | |
| // input | |
| while( scanf( "%d", &n )==1 && n ) { | |
| solve(); | |
| } | |
| return 0; | |
| } |
沒有留言:
張貼留言
任何意見都樂意傾聽