10110 - Light, more light

[Md. Mijanur Rahman]

why TLE???
#include<stdio.h>

int main()
{
long long int n,j,count;

while(scanf("%lld",&n)==1)
{ count=0;
if(n==0)break;
if(n%2==0)
for(j=1;j<=n;j++)
{
if(n%j==0) count++;
}
else for(j=1;j<=n;j+=2)
{
if(n%j==0) count++;
}

if(count%2!=0)printf("yes\n");
else printf("no\n");
}
return 0;
}

[Md. Mijanur Rahman]

why WA plz help

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	double n;
     
	while(scanf("%f",&n)==1)
	{ 
           if(floor(sqrt(n))==ceil(sqrt(n)))
	                                  printf("yes\n");
	  else printf("no\n");
	}
return 0;
}

[sohel]

Code: Select all

if(floor(sqrt(n))==ceil(sqrt(n)))

This condition will not always give you the correct result, since sqrt() of a square number will not give you the exact digits.
I mean, sqrt(25) != 5.00000000000000000000000.

[shahedcsenu]

i cNT UNDERStand the problem...when light on and when off .;.plz anyone can explain it??

[sauro]

i cNT UNDERStand the problem...when light on and when off .;.plz anyone can explain it??

check my earlier post.

[shuvrothpol1]

runtime error...why??? (also tried with long long )

#include <stdio.h>
#include <math.h>
#define N 70000

unsigned int status[N+1]={0},prime[N+1];
void list_prime();
unsigned int primefactor(unsigned int n);

int main ()
{
unsigned int n;
list_prime();
scanf ("%u",&n);
while (n!=0){
if (n%2==0)
printf ("yes\n");
else if (status[n]==0)
printf ("no\n");
else
{
n=primefactor(n)+1;
if (n%2==0)
printf ("no\n");
else
printf ("yes\n");
}
scanf ("%u",&n);
}
return 0;
}

void list_prime() {
unsigned int i, j, sqrtN;

sqrtN = sqrt( N );
for( i = 3; i <= sqrtN; i += 2 ) {
if( status == 0 ) {
for( j = i * i; j <= N; j += i + i )
status[j] = 1;
}
}
prime[0]=2;
status[1]=1;
j=1;
for( i = 3; i <= N; i += 2 ) {
if( status == 0 ){
prime[j++]=i;
}
}
}

unsigned int primefactor(unsigned int n)
{
unsigned int listSize=0,i,j;
unsigned int sqrtN =sqrt(n);
for(i = 0; prime <= sqrtN; i++ ) {
if( n % prime == 0 ) {
while( n % prime == 0 ) {
n /= prime;
listSize++;
}
}
}
if( n > 1 ) {
listSize++;
}
return listSize;
}

[brianfry713]

It looks like you figured it out.

[aybek]

Hi!
Yesterday I have been solving 10110 problem and had wrote this algorithm,
the math model of the problem is very simple, solution is:
if the number of dividers of number is even then we have to print "no",
if odd we have to print "yes":
Here is solution of problem, how did I solve it

1. Get the number of dividers of number
|_1. Factorize number
|_2. Determine the number of dividers
2. If (number of dividers odd) print "yes"
else print "no"

Complexity of factorize algorithm is O(sqrt(n))
Complexity of div_num_of is not even O(n)
If input contains m number, the total complexity will be
O(mn)

Is it slow?

Code:

Code: Select all

#include <iostream>
#include <vector>
#include <cmath>
#include <map>

namespace nums {
	/* function will add factors of the numbers to the end of vector */
	/* TODO: optimizate for loop */
	template <class T>
	bool factorize(T n, std::vector<T> & v) {
		T i, c;
		for (c = n; (c%2) == 0; c /= 2) {
			v.push_back(2);
		}
		for (i = 3; i <= static_cast<T>(sqrt(c)+1.0); ) {
			if ((c % i) == 0) {
				v.push_back(i);
				c /= i;
			} else { i += 2; }
		}
		if (c > 1 && (c != n)) { v.push_back(c); }
		return true;
	}

	/* Returns number of dividers of n */
	template <class T>
	size_t div_num_of(T n) {
		if (n == 0) { return 0; }
		if (n == 1) { return 1; }

		std::vector<T> v, el;
		std::map<T, size_t> d;

		factorize(n, v);
		for (const T & e : v) {
			if (d.find(e) != d.end()) {
				++d[e];
			} else {
				d[e] = 1;
				el.push_back(e);
			}
		}

		size_t dn = 0;
		for (const T & e : el) {
			if (dn == 0) dn = 1;
				dn *= (d[e]+1);
		}
		return dn;
	}
}

int main() {
	using namespace std;
	using namespace nums;

	uint32_t n;
	for (;;) {
		cin >> n;
		if (n == 0) break;

		if (div_num_of(n)%2) {
			cout << "yes\n";
		} else {
			cout << "no\n";
		}
	}

	return 0;
}

[aybek]

problem is not in problem. I need help to count complexity of algorithms

[brianfry713]

You can solve for each input value in constant time using sqrt().

[rafid059]

Can some help me?? im getting a runtime error everytime.

Code: Select all

Accepted   :D

[lighted]

Change line

Code: Select all

int num = s.nextInt();

It must be

Code: Select all

long num = s.nextLong();

Don't forget to remove your code after getting accepted.

[rafid059]

thanks a lot, lighted!

[xrenon]

deleted....thnx

[brianfry713]

Try input:

Code: Select all

4294967295
0