QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556719#9248. An Easy Math Problemzzm666Compile Error//C++143.0kb2024-09-10 20:22:012024-09-10 20:22:01

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:22:01]
  • Judged
  • [2024-09-10 20:22:01]
  • 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;

inline ll multi(ull x, ull y, ll p) {  // O(1)快速乘(防爆long long)
    return (x * y - (ull)((lb)x / p * y) * p + p) % p;
}

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

answer.code:11:1: warning: inline variables are only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   11 | inline ll multi(ull x, ull y, ll p) {  // O(1)快速乘(防爆long long)
      | ^~~~~~
answer.code:11:17: error: ‘ull’ was not declared in this scope; did you mean ‘ll’?
   11 | inline ll multi(ull x, ull y, ll p) {  // O(1)快速乘(防爆long long)
      |                 ^~~
      |                 ll
answer.code:11:24: error: ‘ull’ was not declared in this scope; did you mean ‘ll’?
   11 | inline ll multi(ull x, ull y, ll p) {  // O(1)快速乘(防爆long long)
      |                        ^~~
      |                        ll
answer.code:5:12: error: expected primary-expression before ‘long’
    5 | #define ll long long
      |            ^~~~
answer.code:11:31: note: in expansion of macro ‘ll’
   11 | inline ll multi(ull x, ull y, ll p) {  // O(1)快速乘(防爆long long)
      |                               ^~
answer.code:11:35: error: expression list treated as compound expression in initializer [-fpermissive]
   11 | inline ll multi(ull x, ull y, ll p) {  // O(1)快速乘(防爆long long)
      |                                   ^
answer.code: In function ‘long long int qpow(long long int, long long int, long long int)’:
answer.code:18:31: error: ‘multi’ cannot be used as a function
   18 |         if (b & 1) res = multi(res, a, p);
      |                          ~~~~~^~~~~~~~~~~
answer.code:19:18: error: ‘multi’ cannot be used as a function
   19 |         a = multi(a, a, p);
      |             ~~~~~^~~~~~~~~
answer.code: In function ‘bool miller_rabin(long long int)’:
answer.code:36:22: error: ‘multi’ cannot be used as a function
   36 |             a = multi(a, a, n);
      |                 ~~~~~^~~~~~~~~
answer.code: In function ‘long long int f(long long int, long long int, long long int)’:
answer.code:43:67: error: ‘multi’ cannot be used as a function
   43 | long long f(long long x, long long c, long long p) { return (multi(x, x, p) + c) % p; }
      |                                                              ~~~~~^~~~~~~~~