QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694363#9248. An Easy Math ProblemWaO_o#WA 84ms11828kbC++204.6kb2024-10-31 17:47:092024-10-31 17:47:09

Judging History

This is the latest submission verdict.

  • [2024-10-31 22:36:43]
  • hack成功,自动添加数据
  • (/hack/1098)
  • [2024-10-31 22:13:58]
  • hack成功,自动添加数据
  • (/hack/1096)
  • [2024-10-31 22:00:43]
  • hack成功,自动添加数据
  • (/hack/1095)
  • [2024-10-31 17:47:09]
  • Judged
  • Verdict: WA
  • Time: 84ms
  • Memory: 11828kb
  • [2024-10-31 17:47:09]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define deg( x ) cout<<""#x"="<<x<<endl
#define endl '\n'
#define pll pair<int,int>
#define se second
#define fr first

const int N=1e6+10;

const __int128 ONE=1;

int qmi( int base , int power , int m )// 快速幂求base的power次方,在余m的情况下
{
    int result=1;
    while( power>0 ){
        if( power&1 ){
            result=( ONE*result*base )%m;
        }
        power>>=1;
        base=( ONE*base*base )%m;
    }
    return result;
}

int ut12[ 12 ]={ 2,3,5,7,11,13,17,19,23,29,31,37 };
bool Miller_Rabin( int n ){
    if( n<=37 ){ // 筛掉n小于等于37的质数
        for( int i=0; i<=11; i++ ) if( n==ut12[ i ] ) return true;
        return false;
    }
    if( ( n&1 )^1 ) return false; // 所有偶数判掉

    int u=n-1; int t=0; // 将 n-1 转化成 u*2^t 因为要用二次探测 x^2 % p = 1 % p , x=1\p-1;
    while( ( u & 1 )^1 ) u>>=1 , t++; // t最少是1

    for( int i=0; i<=11; i++ ){
        int a=qmi( ut12[ i ] , u , n );
        if( a==1 || a==n-1 ) continue; // 第一次是n-1\1以后都是1;

        for( int e=1; e<=t; e++ ){ // 一定是形似 a1 , a2 , a3 , n-1 , 1.....1
            a=( ONE*a*a )%n; // 防止爆炸
            if( a==n-1 && e!=t ){ a=1; break;} // 除了最后一次外只要出现n-1 此后 都是1;
            if( a==1 ) return false; // 如果没有出现 n-1 但是出现了 1 二次探测未通过
        }

        if( a^1 ) return false; // 费马定理未通过
    }
    return true;
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); // 最大生成2^32随机数

int gcd( int a , int b )//最大公约数
{
    if( b==0 ) return a;
    return gcd( b , a%b );
}

int f( int x , int c , int m ){
    int re=( ( ONE*x*x )%m + ONE*c )%m;
    return re;
}

int Pollard_Rho( int n ){
    if( n==4 ) return 2;
    if( Miller_Rabin( n ) ) return n; // 特判素数

    while( 1 ){
        int c=rnd()%( n-1 )+1; // 生成1~n-1随机数
        //f随机数产生的特点
        // 取n的最小素数为p; i==j(mod p) f(i)==f(j)(mod p)
        int t=0 , r=0; // 龟兔判环
        int p=1;
        do{
            for( int i=1; i<=128; i++ ){ // 每128个取一次答案
                t=f( t , c , n ); r=f( f( r , c,  n ) , c , n ); // t一倍速 , r二倍速
                int te=( ONE*p*abs( t-r ) )%n;
                if( te==0 ) break;
                p=te;
            }
            int d=gcd( p , n );
            if( d>1 ) return d;
        }while( t!=r );
    }
}

int rho[ N ]; int idxr=0;

void get_fac( int n ){
    idxr=0;

    if( n<=1000 ){
        for( int i=2; i*i<=n; i++ ){
            while( n%i==0 ) n/=i,rho[ ++idxr ]=i;
        }
        if( n^1 ) rho[ ++idxr ]=n;
    }
    else{
        queue<int> q;
        q.push( n );
        while( !q.empty() ){
            int te=q.front(); q.pop();
            int o=Pollard_Rho( te );
            if( o==te ) rho[ ++idxr ]=o; // 是质因子直接取出
            else q.push( o ) , q.push( te/o ); // 否则递归求两个数的质因子
        }
    }

    sort( rho+1 , rho+1+idxr );
}

int idx=0 , idn=0;

int fac[ N ] , num[ N ] , fan[ N ];

void dec( int x ){

    get_fac( x );

    idx=0;
    int e=1;
    while( e<=idxr ){
        int te=rho[ e ];
        int hh=0;
        while( rho[ e ] == te ){
            hh++;
            e++;
            if( e>idxr ) break;
        }

        fac[ ++idx ]=te;
        num[ idx ]=hh;
    }


    idn=1; fan[ 1 ]=1;
    for( int i=1; i<=idx; i++ ){
        int en=idn , te=1;
        int now=fac[ i ];

        for( int k=1; k<=num[ i ]; k++ ){
            te*=now;
            for( int j=1; j<=en; j++ ) fan[ ++idn ]=fan[ j ]*te;
        }

    }

    sort( fan+1 , fan+1+idn );
}

pll A[ N ];

int get( int c , int te ){
    int re=1;

    for( int i=idx-1; i>=0; i-- ){
        if( c>>i&1 ){
            re*=num[ i+1 ];
        }
    }

    re*=( 1<<( te-1 ) );

    re/=2;
    return re;
}

int pan( int x ){
    int re=0;
    for( int i=idx-1; i>=0; i-- ){
        if( x>>i&1 ) re++;
    }

    return re;
}

void solve(){
    int n;
    cin>>n;
    //n=1e10;

    int o=0;
    dec( n );

    int ans=0;

    ans=idn;
    for( int a=0; a<( 1<<idx ); a++ ){
        int te=pan( a );
        if( te < 2 ) continue;
        ans+=get( a , te );
    }


    cout<<ans<<endl;

}

signed main() {
    ios::sync_with_stdio( 0 );
    cout.tie( 0 ); cin.tie( 0 );

    int T=1;
    cin>>T;
    while( T-- ){
        solve();
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11812kb

input:

10
1
2
3
4
5
6
7
8
9
10

output:

1
2
2
3
2
5
2
4
3
5

result:

ok 10 lines

Test #2:

score: -100
Wrong Answer
time: 84ms
memory: 11828kb

input:

2000
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
646969323...

output:

15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
15781
...

result:

wrong answer 1st lines differ - expected: '29525', found: '15781'