ENCNOV11 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Div-2 Contest

Author: Anuska Sinha
Tester: Arnab Chanda
Editorialist: Anuska Sinha

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Math

PROBLEM:

You are given a certain number of bulbs(Say n) which are initially in OFF position. The bulbs are numbered from 1 to n. There will be n current fluctuations in such a way that in the 1st fluctuation all bulbs are toggled, in the 2nd fluctuation every 2nd bulb is toggled, in the 3rd fluctuation every 3rd bulb is toggled and so on. Bulbs with a number divisible by 3 are kept OFF at the end of n fluctuations. Give the final number of bulbs ON in the end.

EXPLANATION:

Only the perfect squares have odd number of factors to them. Hence after the toggles, only the numbers which are perfect squares will be in ON position. Then we need to remove the perfect squares divisible by 3 and give the final count.

SOLUTIONS:

Setter's Solution 
int main()
{
     cin>>t;
   while(t!=0){
       lld n; int count=0;
       cin>>n;
        for(int i = 1; i * i <= n; i++){
           if(i*i% 3 !=0)
             count++;
        }
       cout<<count<<endl;
       t--;
    }
2 Likes