CCFY - EDITORIAL

[PRACTICE][1]

[CONTEST][2]

Author- [Medha Pandey][3]

Tester- [Akanksha Bigasia][4]

Editorialist- [Sanya Tayal][5]

DESCRIPTION

Given an integer N find the GCD for for calculating rows to arrange chocolates in N number of stocks having particular number of choclates arranged in x number of rows.

EXPLANATION :

Calculate GCD for N number of stocks for all natural numbers from 1 to N. Run a loop from 1 to N and number of rows would be sum of all possible numbers for GCD. Final answer is x .

CODE:

	
	int gcd(int a, int b)
	{
		if(a % b==0) return b;			//to calculate GCD
		return gcd(b,a % b);
	}
 	int div[1000001], p, exp;
	long long f1[1000001],f2[1000001],aux,pow;
	int main()
	{
		memset(div,-1,sizeof(div));
    		for(int i = 2;i< =1000000;++i){
    		if(div[i]==-1)
		{
			div[i] = i;
            		             if(i< =1000)
                                        for(int j = i * i;j< =1000000;j += i)
 		              div[j] = i;
        		}
    	}
    	memset(f2,-1,sizeof(f2));
	f1[1] = 0;
	f2[1] = 1;
    	for(int i = 2;i< =1000000;++i)
	{
		p = div[i]; exp = 0;
		aux = i; pow = 1;
	             while(aux%p==0)
		{
            			pow * = p;
	             		++exp;
	                          aux /= p;
              	}
	             f2[i] = ((exp+1)* pow-exp* (pow/p))* f2[aux];
		f1[i] = f1[i-1]+f2[i]-i;
             }
    	int N;
    	while(true){
	scanf("%d",&N);
	if(N==0) break;
	printf("%lld\n",f1[N]);
    }
    


  [1]: https://www.codechef.com/problems/CCFY
  [2]: https://www.codechef.com/IC32016
  [3]: https://www.codechef.com/users/mack8
  [4]: https://www.codechef.com/users/akku_bigasia
  [5]: https://www.codechef.com/users/stayal
//