Uva 10699 - Count the factors
/*
Uva 10699 - Count the factors
Verdict: Accepted
Time : 0.453
*/
/*#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define loop (i,n) for (i=0;i<n;i++)
#define LL long long
#define L long
#define nl puts("")
#define MX 1000005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()
using namespace std;
bool stats[MX];
L vpsz,cnt;
vector <L> vp;
vector <L> facto;
void prime ()
{
L i,j,qrt;
for (i=4;i<=MX;i+=2)
{
stats[i] = true;
}
qrt = (long) sqrt(double(MX));
vp.pb (2);
for (i=3;i<=qrt;i+=2)
{
if (!stats[i])
{
for (j=i*i;j<=N;j+=i+i)
{
stats[j] = true;
}
}
}
for (i=3;i<=MX;i+=2)
{
if (!stats[i])
{
vp.pb (i);
}
}
vpsz = vp.size();
}
void primefacto(L n)
{
L i;
for (i=0;i<vpsz;i++)
{
while (n%vp[i]==0)
{
facto.pb (vp[i]);
n/=vp[i];
if (n==0 or n==1) break;
}
}
}
int main()
{
L n,cnt;
vector <L> dis;
map <L,bool> mp;
prime();
//for (L i=0;i<vpsz;i++) cout << vp[i] << " ";
while (sf("%ld",&n)==1 and n)
{
primefacto(n); cnt=0;
//for (L i=0;i<facto.size();i++) cout << facto[i] << " ";
for (L i=0;i<facto.size();i++)
{
if (!mp[facto[i]])
{
dis.pb(facto[i]);
}
mp[facto[i]] = true;
}
for (L i=0;i<dis.size();i++) cnt++;
pf ("%ld : %ld\n",n,cnt);
facto.clear(); dis.clear(); mp.clear();
}
return 0;
}*/
/*
Uva 10699 - Count the factors
Verdict: Accepted
Time: 0.023
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define loop (i,n) for (i=0;i<n;i++)
#define LL long long
#define L long
#define nl puts("")
#define MX 1000005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()
using namespace std;
bool stats[MX];
L vpsz,cnt;
vector <L> vp;
void prime ()
{
L i,j,qrt;
for (i=4;i<=MX;i+=2)
{
stats[i] = true;
}
qrt = (long) sqrt(double(MX));
vp.pb (2);
for (i=3;i<=qrt;i+=2)
{
if (!stats[i])
{
for (j=i*i;j<=N;j+=i+i)
{
stats[j] = true;
}
}
}
for (i=3;i<=MX;i+=2)
{
if (!stats[i])
{
vp.pb (i);
}
}
vpsz = vp.size();
}
void primefacto(L n)
{
L i;
for (i=0;i<vpsz;i++)
{
if (n%vp[i]==0)
{
cnt++;
while (n%vp[i]==0) // find the prime factors
{
n/=vp[i];
}
if (n==1 or n==0) break;
}
}
}
int main ()
{
L n;
prime();
//for (L i=0;i<vpsz;i++) cout << vp[i] << " ";
while (sf ("%ld",&n) and n)
{
cnt = 0;
primefacto(n);
pf ("%ld : %ld\n",n,cnt);
}
return 0;
}
Uva 10699 - Count the factors
Verdict: Accepted
Time : 0.453
*/
/*#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define loop (i,n) for (i=0;i<n;i++)
#define LL long long
#define L long
#define nl puts("")
#define MX 1000005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()
using namespace std;
bool stats[MX];
L vpsz,cnt;
vector <L> vp;
vector <L> facto;
void prime ()
{
L i,j,qrt;
for (i=4;i<=MX;i+=2)
{
stats[i] = true;
}
qrt = (long) sqrt(double(MX));
vp.pb (2);
for (i=3;i<=qrt;i+=2)
{
if (!stats[i])
{
for (j=i*i;j<=N;j+=i+i)
{
stats[j] = true;
}
}
}
for (i=3;i<=MX;i+=2)
{
if (!stats[i])
{
vp.pb (i);
}
}
vpsz = vp.size();
}
void primefacto(L n)
{
L i;
for (i=0;i<vpsz;i++)
{
while (n%vp[i]==0)
{
facto.pb (vp[i]);
n/=vp[i];
if (n==0 or n==1) break;
}
}
}
int main()
{
L n,cnt;
vector <L> dis;
map <L,bool> mp;
prime();
//for (L i=0;i<vpsz;i++) cout << vp[i] << " ";
while (sf("%ld",&n)==1 and n)
{
primefacto(n); cnt=0;
//for (L i=0;i<facto.size();i++) cout << facto[i] << " ";
for (L i=0;i<facto.size();i++)
{
if (!mp[facto[i]])
{
dis.pb(facto[i]);
}
mp[facto[i]] = true;
}
for (L i=0;i<dis.size();i++) cnt++;
pf ("%ld : %ld\n",n,cnt);
facto.clear(); dis.clear(); mp.clear();
}
return 0;
}*/
/*
Uva 10699 - Count the factors
Verdict: Accepted
Time: 0.023
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define loop (i,n) for (i=0;i<n;i++)
#define LL long long
#define L long
#define nl puts("")
#define MX 1000005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()
using namespace std;
bool stats[MX];
L vpsz,cnt;
vector <L> vp;
void prime ()
{
L i,j,qrt;
for (i=4;i<=MX;i+=2)
{
stats[i] = true;
}
qrt = (long) sqrt(double(MX));
vp.pb (2);
for (i=3;i<=qrt;i+=2)
{
if (!stats[i])
{
for (j=i*i;j<=N;j+=i+i)
{
stats[j] = true;
}
}
}
for (i=3;i<=MX;i+=2)
{
if (!stats[i])
{
vp.pb (i);
}
}
vpsz = vp.size();
}
void primefacto(L n)
{
L i;
for (i=0;i<vpsz;i++)
{
if (n%vp[i]==0)
{
cnt++;
while (n%vp[i]==0) // find the prime factors
{
n/=vp[i];
}
if (n==1 or n==0) break;
}
}
}
int main ()
{
L n;
prime();
//for (L i=0;i<vpsz;i++) cout << vp[i] << " ";
while (sf ("%ld",&n) and n)
{
cnt = 0;
primefacto(n);
pf ("%ld : %ld\n",n,cnt);
}
return 0;
}
Comments
Post a Comment