http://codeforces.com/contest/337/problem/C
得到的分数为：(2^1+2^2+...+2^X)*k + m-X*k = (2^(X+1)-2)*k + m-X*k；
x的确定：max(0, m - (n - n mod k) / k * (k-1) - n mod k)；
为了得到的分数尽可能少，让满足k次的情况发生在前面。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #define ll long long 6 using namespace std; 7 const ll mod=1e9+9; 8 9 ll n,m,k,ans,x; 10 11 ll pow(ll a,ll b) 12 { 13 if(b==0) return 1; 14 ll xx=pow(a,b/2); 15 xx=(xx*xx)%mod; 16 if(b&1) xx=(xx*a)%mod; 17 return xx; 18 } 19 20 ll deal1(int n,int m,int k) 21 { 22 ll x=max(0,m-(n-n%k)/k*(k-1)-n%k); 23 return (mod+m-x*k+(pow(2,x+1)-2)*k)%mod; 24 } 25 int main() 26 { 27 cin>>n>>m>>k; 28 29 cout<<deal1(n,m,k)<<endl; 30 return 0; 31 }