Estou fazendo um programa em C++ para resolver o exercício 2597 de matemática da plataforma URI ONLINE JUDGE segue abaixo a descrição do problema.
Eu comecei a fazer o programa em C++, porém percebam que a entrada é muito grande, tentei fazer uma DP para pré-processar tudo antes, porém não consigo criar um vetor de tamanho 10^9 !! Segue o programa para vocês darem uma olhada **
#include <bits/stdc++.h>
using namespace std;
typedef long long int bigint;
bigint contaDiv(bigint dividendo) {
bigint div = 0;
bigint k = 1;
bigint m = 1;
bigint divisor = 1;
while(divisor<=sqrt(dividendo))
{
if(dividendo%divisor==0)
{
// cout<<"(div/div)"<<(dividendo/divisor)<<endl;
if((dividendo/divisor)==divisor)
{
div+=1;// cout<<"one"<<endl;
}
else
{
div+=2; //cout<<"two"<<endl;
}
}
++divisor;
}
return div;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
bigint c,n,vl;
cin>>c;
while(c--) {
cin>>n;
int ans = 0;
for(int i=1;i<=n;++i) {
// cout<<"DIV de "<<i<<" = "<<contaDiv(i)<<endl;
if(contaDiv(i)%2==0) {
++ans;
}
}
cout<<ans<<endl;
}
return 0;
}
**Se alguém conseguir me dar uma ajuda... como resolver esse problema !! No momento esse código esta recebendo Time Limit Exceed !! **