c - 求幂程序

Question

问题是这个

Nancy hates any and every string that contains the number "13". Clouseau wants to gift her a string and is looking over his options, ofcourse he would never pick a string that has "13" as a substring.

Tell Clouseau the total number of such strings s that are made of exactly N characters. The strings may contain any integer from 0-9, repeated any number of times.

输入: 输入文件的第一行包含一个数字T，表示测试用例的数量。接下来的T行，每行包含一个整数N。

输出: 输出文件应在新行中包含每个查询的答案，以 1000000009 为模。

限制: 1吨100000， 0 N 1000000009

我的逻辑不正确。

# include <stdio.h>
# define MOD 1000000009

unsigned long long mod_pow(unsigned long long num, unsigned long long pow, unsigned long long mod)
{
    unsigned long long test;
    unsigned long long n = num;
    for(test = 1; pow; pow >>= 1) {

        if (pow & 1)
            test = ((test % mod) * (n % mod)) % mod;
        n = ((n % mod) * (n % mod)) % mod;
    }

    return test;
}

int main(int argc, char* argv[])
{

    long t;

    unsigned long long total_no, bad_no, n;

    scanf ("%ld", &t);

    while (t--) {
    
        scanf ("%lld", &n);

        if (n != 1) {
      
            total_no = (10 * (mod_pow (10, n-1, MOD))) % MOD;
    
            bad_no = ((n - 1) * (mod_pow(10, n-2, MOD))) % MOD;

            printf ("%lld\n", (((total_no - bad_no) % MOD)));
        }
        else
            printf ("10\n");

    }
    return 0;
}

Answer 1

您可以使用此功能:

long long int  bigmod ( long long a, long long p, long long m )
{
    if ( p == 0 )return 1; // If power is 0, then a ^ 0 = 1 for any value of a, And 1 Mod m=1 for any value of m, So return 1

    if ( p % 2 ) // If power is odd, Split it : a ^ 5 =( a )* (a ^ 4) --> left and right child respectively.
    {
        return ( ( a % m ) * ( bigmod ( a, p - 1, m ) ) ) % m; 
    }
    else //If power is even then split it equally and return the result...
    {
        long long c = bigmod ( a, p / 2, m ); 
        return ( (c%m) * (c%m) ) % m;
    }
}

并像这样调用这个函数:

int main(){

     // take input....
    //Calling...
    printf("result is %lld\n",bigmod(a,p,MOD)); // 
   return 0;   
}