学步园

数学推导，快速求素数，模拟

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 4000010;
/**
    n = a0^b0 * a1*b1 * a2^b2 * a3^b3 ......
    a均为素数
    因子数量 = (b0+1)*(b1+1)*(b2+1).....
    因子数量为素数：仅有一个素因子且(b0+1)为素数
    因子和 = （1 + a0^1 + a0^2 + ... a0^b0）* (1 + a1^1 + a1^2 + ... a1^b1)
    因子和为素数：仅有一个素因子且（1 + a0^1 + a0^2 + ... a0^b0）为素数
    因子的乘积为 n^x * (n为平方数?n^0.5 : 1)
*/
int isPrim[MAXN];
int prime[MAXN >> 2];
void getPrime()
{
    memset ( isPrim, 1, sizeof isPrim );
    isPrim[0] = isPrim[1] = 0;
    for ( int i = 2; i <= MAXN; ++i )
    {
        if ( isPrim[i] ) { prime[++prime[0]] = i; }
        for ( int j = 1; j <= prime[0] && prime[j]*i <= MAXN; ++j )
        {
            isPrim[prime[j]*i] = 0;
            if ( i % prime[j] == 0 )
            {
                break;
            }
        }
    }
}
ll fc[2][200];
/// 分解质因数
int getFactor ( int x )
{
    ll tmp = x;
    int fnum = 0;
    for ( int i = 1; prime[i]*prime[i] <= tmp; ++i )
    {
        fc[1][fnum] = 0;
        if ( tmp % prime[i] == 0 )
        {
            fc[0][fnum] = prime[i];
            while ( tmp % prime[i] == 0 )
            {
                fc[1][fnum]++;
                tmp /= prime[i];
            }
            fnum++;
        }
    }
    if ( tmp > 1 )
    {
        fc[0][fnum] = tmp, fc[1][fnum++] = 1;
    }
    return fnum;
}
const int MAXM = 1010;
struct node
{
    int a, b;
} c[MAXM];
int d[5], v[16], rest[16];
ll mPow ( ll a, int t )
{
    ll s = 1, tp = a;
    while ( t )
    {
        if ( t & 1 ) { s *= tp; }
        tp *= tp;
        t >>= 1;
    }
    return s;
}
ll getSum ( ll a, ll b )
{
    return ( mPow ( a, b + 1 ) - 1 ) / ( a - 1 );
}
int mmp[16];
int judge ( int dx )
{
    int num = c[dx].a;
    int sn = 0, cnt = 0;
    if ( num == 1 )
    {
        cnt++;
        sn |= 1 << 3;
        v[sn] += c[dx].b;
        mmp[sn] = 1;
        return cnt;
    }
    int fnum = getFactor ( num );
    /// 1
    if ( fnum == 1 && fc[1][0] == 1 ) { cnt++, sn |= 1; }
    /// 2
    if ( fnum == 1 && isPrim[1 + fc[1][0]] ) { cnt++, sn |= 1 << 1; }
    /// 3
    if ( fnum == 1 && isPrim[getSum ( fc[0][0], fc[1][0] )] ) { cnt++, sn |= 1 << 2; }
    /// 4
    int sum = 1, ct = 1, y = 1;
    for ( int i = 0; i < fnum; ++i )
    {
        sum *= fc[1][i] + 1;
    }
    if ( sum & 1 ) { y = sqrt ( ( double ) num ); }
    sum >>= 1;
    if ( sum & 1 ) { ct = num; }
    ct *= y;
    y = sqrt ( ( double ) ct );
    if ( y * y == ct )
    {
        cnt++, sn |= 1 << 3;
    }
    v[sn] += c[dx].b;
    mmp[sn] = cnt;
    return cnt;
}
int rk[16] = {15, 14, 13, 11, 7, 12, 10, 9, 6, 5, 3, 8, 4, 2, 1, 0};
int main()
{
#ifdef  __GNUC__
    freopen ( "in.txt", "r", stdin );
#endif // __GNUC__
    getPrime();
    int t, n, k;
    int i, j, h;
    scanf ( "%d", &t );
    while ( t-- )
    {
        scanf ( "%d%d", &n, &k );
        memset ( v, 0, sizeof v );
        for ( i = 0; i < n; ++i )
        {
            scanf ( "%d%d", &c[i].a, &c[i].b );
            if ( i ) { printf ( " " ); }
            printf ( "%d", judge ( i ) );
        }
        puts ( "" );
        for ( i = 0; i < 4; ++i )
        {
            scanf ( "%d", &d[i] );
        }
        int mxnum = 0x80000000;
        /// 1标志取用
        for ( i = 0; i < ( 1 << 16 ); ++i )
        {
            /// 每个状态先来一发
            int flg = 0, q = k, sum = 0;
            memcpy ( rest, v, sizeof v );
            for ( j = 0; j < 16; ++j )
            {
                if ( i & ( 1 << j ) )
                {
                    if ( rest[j] > 0 )
                    {
                        flg |= j;
                        --q;
                        --rest[j];
                        sum += mmp[j];
                    }
                    else
                    {
                        q = -1;
                        break;
                    }
                }
            }
            flg = 15 & ( ~flg );
            if ( q < 0 ) { continue; }
            for ( j = 0; j < 16 && q; ++j )
            {
                h = rk[j];
                if ( i & ( 1 << h ) )
                {
                    if ( rest[h] <= q )
                    {
                        sum += mmp[h] * rest[h];
                        q -= rest[h];
                        rest[h] = 0;
                    }
                    else
                    {
                        sum += mmp[h] * q;
                        q = 0;
                    }
                }

            }
            if ( !q )
            {
                for ( j = 0; j < 4; ++j )
                    if ( ( 1 << j ) & flg ) { sum += d[j]; }
                mxnum = max ( mxnum, sum );
            }
        }
        printf ( "%d\n", mxnum );
    }
    return 0;
}