題意:
(from luckycat)
解法: 問有幾個數不能跟 n 約分，也就是 n 扣掉能被 n 的因數整除的數，先把 n 質因數分解，假設 n = 12，12 的質因數有 2、3，所以就把 12 扣除 2倍數、3的倍數，由於會重複扣到6的倍數，所以要加回來，也就是排容原理。
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: 10179 - Irreducable Basic Fractions | |
| * Author: Cheng-Shih, Wong | |
| * Date: 2015/04/17 | |
| */ | |
| // include files | |
| #include <iostream> | |
| #include <cstdio> | |
| #include <cstring> | |
| #include <vector> | |
| 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 pb push_back | |
| typedef long long ll; | |
| typedef vector<ll> VLL; | |
| // declarations | |
| ll n; | |
| bool isprime[32005]; | |
| VLL prime; | |
| VLL primefacts; | |
| // functions | |
| void exclusion( int l, VLL::iterator it, bool sign, ll fact, ll &val ) | |
| { | |
| if( l == 0 ) { | |
| ll tmp = n/fact; | |
| if( sign ) tmp = -tmp; | |
| val += tmp; | |
| return ; | |
| } | |
| if( it == primefacts.end() ) return ; | |
| ll f = *it; | |
| ++it; | |
| exclusion( l-1, it, sign, fact*f, val ); | |
| exclusion( l, it, sign, fact, val ); | |
| } | |
| const ll &calc( void ) | |
| { | |
| static ll ans; | |
| static bool sign; | |
| ans = 0LL; | |
| sign = false; | |
| FOR( i, 1, primefacts.size() ) { | |
| exclusion( i, primefacts.begin(), sign, 1LL, ans ); | |
| sign ^= true; | |
| } | |
| return ans; | |
| } | |
| // main function | |
| int main( void ) | |
| { | |
| ll val; | |
| // init | |
| clr( isprime, true ); | |
| prime.clear(); | |
| isprime[0]=isprime[1]=false; | |
| for( ll i=2LL; i<=32000LL; ++i ) if( isprime[i] ) { | |
| prime.pb( i ); | |
| for( ll j=i*i; j<=32000; j+=i ) | |
| isprime[j] = false; | |
| } | |
| // input | |
| while( scanf( "%lld", &n )==1 && n ) { | |
| primefacts.clear(); | |
| val = n; | |
| for( VLL::iterator it=prime.begin(); it!=prime.end(); ++it ) { | |
| if( (*it)*(*it) > val ) break; | |
| if( val%(*it) == 0 ) { | |
| primefacts.pb(*it); | |
| while( val%(*it) == 0 ) | |
| val /= (*it); | |
| } | |
| } | |
| if( val != 1LL ) primefacts.pb(val); | |
| printf( "%lld\n", n-calc() ); | |
| } | |
| return 0; | |
| } |
沒有留言:
張貼留言
任何意見都樂意傾聽