QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692084#9248. An Easy Math ProblemWaO_o#TL 1ms5608kbC++201.7kb2024-10-31 13:47:032024-10-31 13:47:03

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 13:47:03]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 5608kb
  • [2024-10-31 13:47:03]
  • 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=1e5+10;

int gcd( int a , int b ){
    if( b==0 ) return a;
    return gcd( b , a%b );
}

int idx=0 , idn=0;

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

void dec( int x ){
    idx=0;

    //fac[ ++idx ]=1 , num[ idx ]=1;
    for( int i=2; i*i<=x; i++ ){
        if( x%i==0 ) fac[ ++idx ]=i , num[ idx ]=0;
        while( x%i==0 ){
            num[ idx ]+=1;
            x/=i;
        }
    }

    if( x!=1 ) fac[ ++idx ]=x , num[ idx ]=1;

    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 );

}

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

    dec( n );

    int ans=0;
    map< pair<int,int> , int > mp;
    for( int i=1; i<=idn; i++ ){
        int p=fan[ i ];
        //cout<<p<<" ";
        for( int j=i; j<=idn; j++ ){
            int q=fan[ j ];
            if( p*q > n ) break;
            else if( n%( p*q )==0 ){
                int g=gcd( p , q );
                p/=g , q/=g;
                if( mp[ { p  ,q } ]==0 ){
                    mp[ { p , q } ]=1;
                    ans++;
                }
            }
        }
    }

    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5608kb

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
Time Limit Exceeded

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:


result: