Submission #24159

---

Source Code Expand

// compile with "g++ XXX.cc -mno-cygwin -O2" in Cygwin

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>
#include<bitset>
#include<cassert>

using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define FOR3(i,a,b) for(int i=a,i##_end=b;i<i##_end;i++)
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define CLS(x,val) memset((x) , val , sizeof(x)) 
typedef long long ll_t;
typedef long double ld_t;
typedef vector<int> VI; 
typedef vector<VI> VVI;
typedef complex<int> xy_t;

template<typename T> void debug(T v , string delimiter = "\n")
{ for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++) cout << *it << delimiter; cout << flush ;}

int dx[]  = {0,1,0,-1};
int dy[]  = {1,0,-1,0};
string ds = "SENW";

const double PI = 4.0*atan(1.0);

ll_t exgcd(ll_t a, ll_t b, ll_t &x, ll_t &y)
{
  if(b == 0) {
    x = 1; y = 0;
    return a;
  } else {
    ll_t d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
  }
}

// 逆元
ll_t inv(ll_t a, ll_t mod) {
  ll_t x, y;
  if (exgcd(a, mod, x, y) == 1){
    return (x + mod) % mod;
  }
  else {
    return -1;
  }
}

ll_t fact[200000];
int mod = 1000000007;

ll_t choose_mod(int s , int t) // O(1) , mod is prime
{
  if(s<0 || t<0) return 0 ;
  if(s < t) return 0 ;
  return fact[s]*inv(fact[t],mod)%mod*inv(fact[s-t],mod)%mod;
}

vector<int> element(int n)
{
  VI p ;
  for(int x=2;x*x<=n;x++){
    int cnt = 0;
    while(n % x == 0){
      cnt++;
      n /= x;
    }
    if(cnt) p.push_back(cnt);
  }
  if(n>1) p.push_back(1);
  return p;
}

int main() {
  fact[0]=1;
  FOR(i,200000) if(i) fact[i] = fact[i-1] * i % mod;

  ll_t N,M;
  cin>>N>>M;
  if(N < 0) N = -N;
  
  vector<int> e = element(N);
  ll_t base = 1;
  if(SZ(e) && M > 1){
    FOR(i,SZ(e)){
      int all = e[i] + M - 1;
      //cout<<all<<" "<<e[i]<<" "<< choose_mod(all , e[i])<<endl;
      base *= choose_mod(all , e[i]) * choose_mod(all - e[i] , M - 1) ;
      base %= mod;
    }
  }
  //cout<<base<<endl;
  ll_t p = 0;
  for(int i = 0 ; i <= M ; i += 2){
    p = (p + choose_mod(M , i)) % mod;
    //cout<<i<<" "<<choose_mod(M , i) <<endl;
  }
  base = base * p % mod;
  cout<<base<<endl;

  return 0 ;
}

Submission Info

Judge Result