这题就是个组合数而已hh..
C(n,m)=C(n,n-m).然后就是最多sqrt(n)解决吧~还是水题舒服.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=999911659;
const ll N=2e3;
ll yz[N];
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

ll C(ll a,ll b)
{
    if(b>a-b) b=a-b;
    ll res=1,ans=1;
    for(ll i=2;i<=b;i++)    res=res*i%mod;
    ll lv=qp(res,mod-2);
    for(int i=a;i>a-b;i--)
    {
        ans=ans*i%mod;
    }
    return ans*lv%mod;//=ans*lv%mod;
}

int main()
{
    ll n,q,g=0;
    cin>>n>>q;
    for(ll i=1;i*i<=n;i++)
    {
        if(n%i==0) {yz[g++]=i;if(i!=n/i) yz[g++]=n/i;}
    }
    ll res=0;
    for(ll i=0;i<g;i++)
    {
        res+=C(n,yz[i]);
       // cout<<yz[i]<<' '<<C(n,yz[i])<<endl;
    }
    ll ans=qp(q,res);
    cout<<ans<<endl;
    return 0;
}

被打脸了,呜呜呜...
仔细想想处理确实不对,因为q^p%mod!=q^(p%mod)%mod.
下面讲正解:
题目要求: q^p % mod.
mod是质数,由费马小定理可知q^(mod-1)%mod=1.然后就是求q^(p%(mod-1))%mod.因为组合数p很大会爆,所以要进行取模运算.但是组合数取模又存在/数问题,非质数逆元可求,但是不保证p和mod-1互质,这个就很麻烦了.做法还是有,exlucas..hh其实不用,做法就是把mod-1进行质因子分解出来4个数分别是:2 3 4679 35617.令p%(mod-1)=x.p%2=b1.p%3=b2.p%4679=b3.p%35617=b4.下面就是4个方程了.

x%2=b1.
x%3=b2.
x%4679=b3.
x%35617=b4.

用中国剩余定理解出x即可.中国剩余定理前面博客已经有了.
然后lucas大家知道模板就行了hh,证明以后变强了再看.
然后代码如下:

ll lucas(ll n,ll m)
{
     if(m==0)
         return 1;
     else
         return (ll)lucas(n/p,m/p)*c(n%p,m%p)%p;
}

ac代码如下:

// 2 3 4679 35617
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//const ll mod=999911659;
ll a[4]={2,3,4679,35617};//模数
ll b[4];//余数
ll m[4];
ll t[4];
ll qp(ll aa,ll bb,ll mod)
{
    ll res=1;
    while(bb)
    {
        if(bb&1) res=res*aa%mod;
        aa=aa*aa%mod;
        bb>>=1;
    }
    return res;
}

ll C(ll n,ll m,ll mod)
{

    if(m>n) return 0;
    if(n-m<m) m=n-m;
    ll res=1;
    for(ll i=n;i>n-m;i--)
    {
        res=res*i%mod;
    }
    ll sum=1;
    for(ll i=m;i>=2;i--)
    {
        sum=sum*i%mod;
    }sum=qp(sum,mod-2,mod);
    return res*sum%mod;
}

ll lucas(ll n,ll m,ll mod)
{
    if(m==0) return 1;
    else return lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod;
}

ll get(ll x,ll n)
{
    ll res=0;
    for(ll i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            res=(res+lucas(n,i,x))%x;
            if(i*i==n) continue;
            res=(res+lucas(n,n/i,x))%x;
        }
    }
    return res;
}

int main()
{
    ll n,q;
    cin>>n>>q;
    ll M=999911659ll-1ll;
    if(q==M+1ll) {puts("0"); return 0;}
    //得到他们的lucas
    b[0]=get(a[0],n);b[1]=get(a[1],n);b[2]=get(a[2],n);b[3]=get(a[3],n);
    for(ll i=0;i<4;i++) m[i]=M/a[i];
    for(ll i=0;i<4;i++)
    {
        t[i]=qp(m[i],a[i]-2,a[i]);
    }
    ll ans=0;
    for(int i=0;i<4;i++)
    {
        ans+=t[i]*m[i]*b[i];
    }
    cout<<qp(q,ans,999911659ll)<<endl;
    return 0;
}