PREE02 - Editorial

desc2013
easy
editorial
simple-math

#1

Problem Link:

Contest

Difficulty:

Easy

Pre-Requisites:

Basic Mathematics

Problem:

Find all special devisors of given number N, where special number is one from which we can delete digits from any location to get a number cantaining only 3, 5 or 6.

Explaination:

We know that all devisors of any number can be found from 1 to square root of n. So start testing each of them and if the number devides N then check if it contains at least one of 3, 5 or 6, if yes then increase the counter of number of special devisors.

So the algo for this problem is:

Take number N as input
int number = 0;
for i=2 to square root of n, repeat:
	if i devides n then:
		k1 = i, k2 = n/i;
	check if k1 has at least one of 3, 5, 6
		if so number = number+1;
	if k2!=k1, check if k2 has at least one of 3, 5, 6
		if so number = number+1;
check if N contains 3, 5 or 6, if so number = number+1;
print number;
actual Program is:
#include &ltcstdio&gt
#include &ltcmath&gt
using namespace std;
int main()
{
    int k;
    long number=0;
    int t,temp;
    long  div,n;
    scanf("%d",&t);
    while(t--)
    {
        number=0;
        scanf("%ld",&n);
        for(int i=2;i<=sqrt(n);i++)
        {
             k=i;
             if(n%k==0)
            {
             div=n/i;
              while(k!=0)
              {
                  temp=k%10;
                  k=k/10;
                  if(temp==3||temp==5||temp==6)
                  {
                      number++;
                      break;
                  }
              }
              if(div!=i)
              while(div!=0)
              {
              temp=div%10;
              div=div/10;
              if(temp==3||temp==5||temp==6)
              {
                  number++;
                  break;
              }
          }
        }
    }
    while(n!=0)
          {
              temp=n%10;
              n=n/10;
              if(temp==3||temp==5||temp==6)
                {
                    number++;
                    break;
                }

          }
printf("%ld

",number);
}
}