題意:
(from luckycat)
解法:
排容原理，如 http://mobcs.blogspot.tw/2015/04/uva-10179-irreducable-basic-fractions.html 。
但是需要搭配最小公倍數 LCM。
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: 10325 - The Lottery | |
| * Author: Cheng-Shih, Wong | |
| * Date: 2015/06/17 | |
| */ | |
| // 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) ) | |
| typedef long long ll; | |
| typedef vector<ll> VLL; | |
| // declarations | |
| ll n, m; | |
| VLL num; | |
| // functions | |
| void input( void ) | |
| { | |
| ll v; | |
| num.clear(); | |
| FOR( i, 1, m ) { | |
| scanf( "%lld", &v ); | |
| num.push_back( v ); | |
| } | |
| } | |
| inline ll gcd( ll a, ll b ) | |
| { | |
| return ( b ? gcd(b,a%b):a ); | |
| } | |
| inline ll lcm( ll a, ll b ) | |
| { | |
| return (a/gcd(a,b))*b; | |
| } | |
| void solve( void ) | |
| { | |
| ll ans = n; | |
| ll stt = (1<<m)-1; | |
| ll val; | |
| int cnt; | |
| FOR( i, 1, stt ) { | |
| cnt = 0; | |
| val = 1; | |
| FOR( j, 0, m-1 ) { | |
| if( (i&(1<<j)) ) { | |
| val = lcm( val, num[j] ); | |
| ++cnt; | |
| } | |
| } | |
| val = n/val; | |
| if( cnt&1 ) | |
| val = -val; | |
| ans += val; | |
| } | |
| printf( "%lld\n", ans ); | |
| } | |
| // main function | |
| int main( void ) | |
| { | |
| // input | |
| while( scanf( "%lld%lld", &n, &m )==2 ) { | |
| input(); | |
| solve(); | |
| } | |
| return 0; | |
| } |
there is a very easy process.apply inclusion-exclusion principle & then backtrack.your code is so complicated.
回覆刪除see my 10 line code.
#include
#define ll long long
using namespace std;
int ara[15];
ll N,m;
ll LCM(ll a,ll b)
{
return a/__gcd(a,b)*b;
}
ll backtrack(ll n,ll div)
{
if(n==m) return (N/div);
return backtrack(n+1,div)-backtrack(n+1,LCM(div,ara[n]));
}
int main()
{
while(cin>>N>>m)
{
for(int i=0;i>ara[i];
cout<<backtrack(0,1)<<endl;
}
return 0;
}
Hi Khan Hasan:
刪除Thank you for your comment!
Backtrack seems a better way to do inclusion-exclusion.
I'll try it next time.
But your code is incomplete in the comment.