Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一发代码

Posted by litianci1223 at 2018-11-02 17:56:56 on Problem 3904
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#define rep( i, a, n ) for( int i = a; i < n; i++ )
#define per( i, a, n ) for( int i = n - 1; i >= a; i-- )
#define mem( f, x ) memset( f, x, sizeof( f ) )
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define e 2.71828
using namespace std;
const int N = 10050;
const int M = 20;
const int MAX = 1e4 + 50;
const ll inv = 500000004;
const double g = 9.80;
const double PI = acos( -1.0 );
ll su[M];
ll ct[N], flag[N];
ll ans, mx;
int cnt;
ll getc( ll x ){
    if( x < 4 ) return 0;
    return x*(x-1)*(x-2)*(x-3)/24;
}
void dfs( int cur, int num, ll sum ){
    if( cur > cnt ) return;
    ct[sum]++;
    if( num&1 ) flag[sum] = -1;
    else flag[sum] = 1; 
    for( int i = cur + 1; i < cnt; i++ )
        dfs( i, num + 1, sum*su[i] );
}

int main( ){
    int n;
    ll x;
    while( scanf( "%d", &n ) != EOF ){
        mx = -1, ans = getc( n );
        mem( flag, 0 );
        mem( ct, 0 );
        for( int i = 0; i < n; i++ ){
            cnt = 1;
            scanf( "%lld", &x );
            mx = max( mx, x );
            ll tmp = x;
            for( ll j = 2; j*j <= tmp; j++ ){
                if( tmp%j == 0 ){
                    
                    su[cnt++] = j;
                    while( tmp%j == 0 ) tmp/=j;
                    if( tmp <= 1 ) break;
                }
            }
            if( tmp > 1 ) su[cnt++] = tmp;
            
            for( int i = 1; i < cnt; i++ )
                dfs( i, 1, su[i] );
        }
        
        for( int i = 2; i <= mx; i++ ){
            if( ct[i] >= 4 )
                ans += flag[i]*getc( ct[i] );
        }
        printf( "%lld\n", ans );
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator