QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556700#9248. An Easy Math Problemzzm666TL 814ms3692kbC++143.0kb2024-09-10 20:16:102024-09-10 20:16:10

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-09-10 20:16:10]
  • Judged
  • Verdict: TL
  • Time: 814ms
  • Memory: 3692kb
  • [2024-09-10 20:16:10]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long
#define ld long double

vector<ll> a;
set<ll> st;

long long multi(long long a, long long b, long long p) {
    long long res = a * b % p;
    return res;
}

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    while (b) {
        if (b & 1) res = multi(res, a, p);
        a = multi(a, a, p);
        b >>= 1;
    }
    return res;
}

int test_time = 20;//1/4的概率误判, 最好8次以上 

bool miller_rabin(long long n) {//test_time * logn判断是否为素数 记得加上面的龟速乘和快速幂 
    if (n < 3 || n % 2 == 0) return n == 2;
    long long b = n - 1, k = 0, j;
    while (b % 2 == 1) b /= 2, ++k;
    for (int i = 0; i < test_time; ++i) {
        long long a = qpow(rand() % (n - 2) + 2, b, n);
        if (a == 1) continue;
        for (j = 0; j < k; ++j) {
            if (a != n - 1) break;
            a = multi(a, a, n);
        }
        if (j == k) return 0;
    }
    return 1;
}

long long f(long long x, long long c, long long p) { return (multi(x, x, p) + c) % p; } 

long long pollard_rho(long long N, long long c) {//启发式分解质因数, 单次操作找到一个质因子 记得加上面的函数或手敲 
    long long xi = rand() % (N - 1) + 1, xj = f(xi, c, N);
    while (xi != xj) {
        long long d = __gcd(xi - xj, N);
        if (d > 1) return d;
        xj = f(f(xj, c, N), c, N);
        xi = f(xi, c, N);
    }
    return N;
}

void factor(long long N, std::map<long long, int> &factors) {//启发式分解质因数找到所有质因子,记得加函数 
    if (miller_rabin(N)) ++factors[N];
    else {
        long long c = rand() % (N - 1) + 1;
        long long d = N;
        while (d >= N)
            d = pollard_rho(N, c--);
        factor(N / d, factors);
        factor(d, factors);
    }
}

void solve(){
	ll n, nn;
	cin >> n;
//	n = 6469693230ll;
//	n = 479001600ll * 13;
	nn = n;
	ll i;
	map<ll, int> mp;
	st.clear();
	a.clear();
	if(n != 1) factor(nn, mp);
	
	for(i = 1 ; i * i <= n ; i ++) {
		if(n % i == 0) {
			a.push_back(i);
			a.push_back(n / i);
//			cout << i << ' ';
//			st.insert(i);
//			st.insert(n / i);
		}
//		cout << i << ' ';
 	}
 	for(i = 0 ; i < a.size() ; i ++) {
 		st.insert(a[i]);
// 		if(a[i] != st[st.size() - 1] || st.size() == 0) st.push_back(a[i]);
	}
	st.erase(1);
	ll ans = 0;
	for(auto &it1:st) {
		ll sum = 1;
		for(auto &it2:mp) {
			if(it1 % it2.first == 0) continue;
			sum *= (it2.second + 1); 
		}
		ans += sum - 1;
//		cout << sum - 1 << ' ';
	}
	ans /= 2;
//	cout << "ans = " << ans << ' ';
	ll sum = 1;
	for(auto &it:mp) {
		sum *= (it.second + 1);
//		ans += (it.second + 1);
//		cout << it.first << ' ' << it.second << endl;
	}
	cout << ans + sum << endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
	cin>>t;
	for(int i=1;i<=t;i++){
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 814ms
memory: 3692kb

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:

29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
...

result:

ok 2000 lines

Test #3:

score: -100
Time Limit Exceeded

input:

2000
1763047095
79735483
1016286871
2864801397
2327774116
2668010360
3469893354
3634459021
1613699068
781737219
574741575
2763134701
1458502604
1822260248
2281150332
2924219311
2493931196
3735904708
158802001
2006921221
729928782
1974841034
727412600
2873393292
1291087179
2741607663
1893408215
29827...

output:


result: