title: Recursive and no-recursive get different answer
body: <p>Sorry that my first language is not English.</p>
  
  <p>The homework is about calculate modulus. The dividend is so big(a^y, a and y may be 10^18) so that I should use the Formula: (m * n)%d=(m%d * n%d)%d to finish that.</p>
  
  <p>So my logic is below:</p>
  
  <p>if y=0, return 1%d</p>
  
  <p>if y=1, return a%d</p>
  
  <p>if y is even, return recursive and let m=n=a^(y/2)</p>
  
  <p>if y is  odd, return recursive and let m=x^(y-1) n=a</p>
  
  <p>the problem is: for y is odd, there is two different way to solve the x:</p>
  
  <ul>
  <li><p>1: calculate it directly (a%d)</p></li>
  <li><p>2: use recursive and the power is 1</p></li>
  </ul>
  
  <p>You can see my code in below. In the ~~  ~~, if fill in "a%d" is correct but "remain(1)" is wrong.</p>
  
  <p>But only method 1 the answer is correct.</p>
  
  <p>In also using method 1 also can get the correct answer. I still want to know why using method 2 is wrong?
  So how to solve the problem by using method 2? If can, how should I modify the code? I cannot, why?</p>
  
  <p>I have been tried to print the sub-answer in any recursive with 2 different methods. I see that method 2 while y is odd its sub-answer is wrong, it may return a negative value.</p>
  
  <p>This is my code is below:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  long long int a,i,d;
  
  int remain(long long int y){
    if(y==0) return 1%d;
    else if(y==1) return a%d;
    else if(y%2==0) {long long int temp=remain(y/2); return (temp*temp)%d;}
    else if(y%2==1) return ((remain(y-1))*(~~remain(1)~~))%d;
   }
  
  int main(void){
    scanf("%lld %lld %lld",&amp;a,&amp;i,&amp;d);
    printf("%lld\n",remain(i));
    return 0;
  } 
  </code></pre>
  
  <p>if input 16777215 16777215 23842982</p>
  
  <p>Method 1 answer is 6647725(correct).</p>
  
  <p>Method 2 answer is 12467225(wrong).</p>
  
  <p>TA and I don' t know why method 2 is wrong. My TA suggests me ask this question in here. Thanks a lot.</p>