C(clang11) 解法, 执行用时: 2ms, 内存消耗: 368K, 提交时间: 2021-03-07 19:58:08

#include<stdio.h>
#define ll long long
ll mod=1e9+9,res;
ll ksm(ll x,ll p)
{
	ll ans=1;
	while(p) {
		if(p&1) ans=ans*x%mod;
		x=x*x%mod;
		p>>=1;
	}
	return ans;
}
int main()
{
	int n,m,k;
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		int w=n-m;
		if(w>=n/k)
        {
            printf("%d\n",m);
            continue;
        }
        int t=n/k-w;
		res=((ksm(2,t+1)-2)*k+m-t*k+2*mod)%mod;
		printf("%lld\n",res);
	}
}

C++(clang++11) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2021-03-09 16:25:57

#include<bits/stdc++.h>
using namespace std;
const int w=1e9+9;
int main()
{

    int n,m,k,i,cnt=0,h=0;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=m;i++)
    {
       cnt++;
       h++;
       if(cnt==k)
       {
           h=(h*2)%w;
           cnt=0;
       }

    }
    printf("%d\n",h%w);
    return 0;

}