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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

wa了一整天,n个因子相乘算成了n个因子相加,QAQ, 贴份ac代码

Posted by litianci1223 at 2018-09-30 21:17:57 on Problem 2429
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <time.h>
#define ll long long
#define ull unsigned long long
#define rep( i, a, n ) for( ull i = a; i < n; i++ )
#define per( i, a, n ) for( ull i = n - 1; i >= a; i-- )
#define mem( f, x ) memset( f, x, sizeof( f ) )
#define pii pair<int, int>
#define fi first
#define se second
#define MOD 8191
#define INF 0x3f3f3f3f
#define e 2.71828
using namespace std;
const int N = 100;
const int M = 150;
const int MAX = 5;
const ull inv = 500000004;
const double g = 9.80;
const double PI = acos( -1.0 );
ull s = 20, cnt, ct;
ull A, B;
ull num[N], su[N];
ull ans;

ull gcd( ull a, ull b ){
    return b==0?a:gcd( b, a%b );
}

ull q_mul( ull x, ull y, ull mod ){
    x %= mod, y %= mod;
    ull ret = 0;
    while( y ){
        if( y&1 ) ret = ( ret + x ) % mod;
        x = ( x + x ) % mod;
        y >>= 1;
    }
    return ret;
}

ull q_pow( ull x, ull y, ull mod ){
    if( y == 0 ) return 1ull;
    x %= mod;
    if( y == 1 ) return x;
    ull ret = 1;
    while( y ){
        if( y&1 ) ret = q_mul( ret, x, mod );
        x = q_mul( x, x, mod );
        y >>= 1;
    }
    return ret;
}

bool Judge( ull x, ull y, ull p , ull t ){
    ull ret = q_pow( x, y, p );
    ull pre = ret;
    rep( i, 0, t ){
        ret = q_mul(ret, ret, p );
        if( ret == 1 && pre != 1 && pre != p-1 )
            return 1;
        pre = ret;
    }
    if( ret != 1 ) return 1;
    return 0;
}

bool miller( ull n ){
    if( n <2 ) return 0;
    if( n == 2 ) return 1;
    if( (n&1) == 0 ) return 0;
    ull mod = n -1, t = 0;
    while( ( mod & 1 ) == 0 ) t++, mod>>=1;
    srand(( ull )12234336);
    rep( i, 0, s ){
        ull x = rand( ) % ( n - 2 ) + 2;
        if( Judge( x, mod, n, t ) )
            return 0;
    }
    return 1;
}

ull Floyed( ull n, ull c ){
    ull i = 1, j = 2;
    ull x = rand() % ( n -1 ) + 1, y = x;
    while( 1 ){
        i++;
        x = ( q_mul( x, x, n ) + c ) % n;
        ull p = gcd(( y - x + n ) % n, n );
        if( p != 1 && p != n )
            return p;
        if( x == y ) return n;
        if( i == j ) y = x, j <<= 1;
    }
}

void Find( ull n, ull c ){
    if( n == 1 ) return;
    if( miller(n) ){
        num[cnt++] = n;
        return;
    }
    ull x = n, k = c;
    while( x == n ) x = Floyed( x, c-- );
    Find( n/x, k );
    Find( x, k );
}

void dfs( ull st, ull cmt, ull sum, ull c, ull x ){
    if( sum * sum > x ) return;
    if( cmt == c ){
        ull tp = x / sum;
        if( ans > tp + sum ){
            ans = tp + sum;
            A = sum, B = tp;
            if( A > B ) swap( A, B );
        }
        return;
    }
    for( ull i = st + 1; i <= ct; i++ ){
        dfs( i, cmt + 1, sum * su[i], c, x );
    }
}

int main( ){
    ull m, n;
    while( scanf( "%lld %lld", &m, &n ) != EOF ){
        mem( num, 0 );
        if( m == n ){
            printf( "%lld %lld\n", m, n );
            continue;
        }
        ull tmp = n / m;
        cnt = 1, ans = ( 1ull<<62 );
        Find( tmp, 180 );
        sort( num + 1, num + cnt );
        ull pre = num[1];
        su[1] = num[1], ct = 1;
        rep( i, 2, cnt ){
            if( num[i] != pre )
                pre = num[i], su[++ct] = num[i];
            else
                su[ct] *= num[i];
        }
        if( ct == 1 ){
            printf( "%lld %lld\n", m, n );
            continue;
        }
        rep( i, 1, ct )
            dfs( 0, 0, 1, i, tmp );
        printf( "%lld %lld\n", A*m, B*m );
    }
    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