Submission #3511107
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <list>
#include <cassert>
#include <csetjmp>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define EPS 1e-9
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(x > y) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
vector<bool> isprime;
vector<int> primes;
void sieve(int n){
if((int)isprime.size() >= n+1) return;
isprime.assign(n+1, true);
isprime[0] = isprime[1] = false;
int sqrtn = (int)(sqrt(n * 1.) + .5);
for(int i = 2; i <= sqrtn; i ++) if(isprime[i]) {
for(int j = i * i; j <= n; j += i)
isprime[j] = false;
}
primes.clear();
for(int i = 2; i <= n; i ++) if(isprime[i])
primes.push_back(i);
}
void primeFactors(int x, vector<pair<int,int> > &out_v) {
out_v.clear();
int sqrtx = (int)(sqrt(x*1.) + 10.5);
sieve(sqrtx);
each(p, primes) {
if(*p > sqrtx) break;
if(x % *p == 0) {
int t = 1;
x /= *p;
while(x % *p == 0) {
t ++;
x /= *p;
}
out_v.push_back(make_pair(*p, t));
}
}
if(x != 1) out_v.push_back(make_pair(x, 1));
}
template<int MOD>
struct ModInt {
static const int Mod = MOD;
int x;
ModInt(): x(0) { }
ModInt(signed sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; }
ModInt(signed long long sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; }
int get() const { return x; }
ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const {
long long a = x, b = MOD, u = 1, v = 0;
while(b) {
long long t = a / b;
a -= t * b; std::swap(a, b);
u -= t * v; std::swap(u, v);
}
return ModInt(u);
}
};
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
ModInt<MOD> r = 1;
while(k) {
if(k & 1) r *= a;
a *= a;
k >>= 1;
}
return r;
}
typedef ModInt<1000000007> mint;
vector<mint> factinv;
void nCr_smallR_computeFactinv(int N) {
factinv.resize(N+1);
mint fact = 1;
rer(i, 1, N) fact *= i;
factinv[N] = fact.inverse();
for(int i = N; i >= 1; i --) factinv[i-1] = factinv[i] * i;
}
mint nCr_smallR(int n, int r) {
mint x = 1;
rep(i, r)
x *= n-i;
x *= factinv[r];
return x;
}
int main() {
nCr_smallR_computeFactinv(30);
int N, M;
scanf("%d%d", &N, &M);
N = abs(N);
vector<pair<int,int> > factors;
primeFactors(N, factors);
vector<mint> partitions(31);
rer(i, 0, 30) partitions[i] = nCr_smallR(i+M-1, i);
mint ans = 1;
each(i, factors) ans *= partitions[i->second];
ans *= mint(2) ^ (M - 1);
cout << ans.get() << endl;
return 0;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:138:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_max.txt, 00_max2.txt, 00_max3.txt, 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 01_rnd_21.txt, 01_rnd_22.txt, 01_rnd_23.txt, 01_rnd_24.txt, 01_rnd_25.txt, 01_rnd_26.txt, 01_rnd_27.txt, 01_rnd_28.txt, 01_rnd_29.txt, 04_primes_01.txt, 04_primes_02.txt |
Case Name |
Status |
Exec Time |
Memory |
00_max.txt |
AC |
1 ms |
256 KB |
00_max2.txt |
AC |
1 ms |
256 KB |
00_max3.txt |
AC |
1 ms |
256 KB |
00_min.txt |
AC |
1 ms |
256 KB |
00_sample_01.txt |
AC |
1 ms |
256 KB |
00_sample_02.txt |
AC |
1 ms |
256 KB |
00_sample_03.txt |
AC |
1 ms |
256 KB |
00_sample_04.txt |
AC |
1 ms |
256 KB |
01_rnd_00.txt |
AC |
1 ms |
256 KB |
01_rnd_01.txt |
AC |
1 ms |
256 KB |
01_rnd_02.txt |
AC |
1 ms |
256 KB |
01_rnd_03.txt |
AC |
1 ms |
256 KB |
01_rnd_04.txt |
AC |
1 ms |
256 KB |
01_rnd_05.txt |
AC |
1 ms |
256 KB |
01_rnd_06.txt |
AC |
1 ms |
256 KB |
01_rnd_07.txt |
AC |
1 ms |
256 KB |
01_rnd_08.txt |
AC |
1 ms |
256 KB |
01_rnd_09.txt |
AC |
1 ms |
256 KB |
01_rnd_10.txt |
AC |
1 ms |
256 KB |
01_rnd_11.txt |
AC |
1 ms |
256 KB |
01_rnd_12.txt |
AC |
1 ms |
256 KB |
01_rnd_13.txt |
AC |
1 ms |
256 KB |
01_rnd_14.txt |
AC |
1 ms |
256 KB |
01_rnd_15.txt |
AC |
1 ms |
256 KB |
01_rnd_16.txt |
AC |
1 ms |
256 KB |
01_rnd_17.txt |
AC |
1 ms |
256 KB |
01_rnd_18.txt |
AC |
1 ms |
256 KB |
01_rnd_19.txt |
AC |
1 ms |
256 KB |
01_rnd_20.txt |
AC |
1 ms |
256 KB |
01_rnd_21.txt |
AC |
1 ms |
256 KB |
01_rnd_22.txt |
AC |
1 ms |
256 KB |
01_rnd_23.txt |
AC |
1 ms |
256 KB |
01_rnd_24.txt |
AC |
1 ms |
256 KB |
01_rnd_25.txt |
AC |
1 ms |
256 KB |
01_rnd_26.txt |
AC |
1 ms |
256 KB |
01_rnd_27.txt |
AC |
1 ms |
256 KB |
01_rnd_28.txt |
AC |
1 ms |
256 KB |
01_rnd_29.txt |
AC |
1 ms |
256 KB |
04_primes_01.txt |
AC |
1 ms |
256 KB |
04_primes_02.txt |
AC |
1 ms |
256 KB |