QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556710#9248. An Easy Math Problemzzm666TL 0ms3572kbC++143.1kb2024-09-10 20:19:462024-09-10 20:19:47

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:19:47]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3572kb
  • [2024-09-10 20:19:46]
  • 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 = 0;
    while (b) {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    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 = 16;//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: 3572kb

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: