salve stavo tentando di risolvere il problema armadio delle preoii 2021 e praticamente ho individuato una soluzione che si basa sulla relazione tra gcd e n: gcd è un suo divisore. però la mia soluzione fa solo 29 a causa del tempo, qualcuno saprebbe darmi qualche suggerimento?
#include <bits/stdc++.h>
using namespace std;
long long solve(int);
void evadi(int Q, vector<int>& N) {
long long conta;
for(int i=0; i<Q; i++){
conta=solve(N[i]);
N[i]=conta;
}
}
long long solve(int n){
long long com=0;
for(int i=1; i<=n/2; i++){
if(n%i==0){
if(n/i==3) com++;
else{
int sum=n-i;
if(__gcd(i, sum-i)==i&&i!=sum){
int k=sum;
for(int j=1; j<k; j++){
if(__gcd(j,k-1)==i) com+=2;
k--;
}
}
}
}
}
return com;
}