Submission #3258921


Source Code Expand

Copy
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
lint invMod(lint a, lint m) {
  lint x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;return 0;
}
vector<lint> zyo,rz;
lint mo=1000000007;
lint co(int a,int b){
	if(a<0 || b<0 || a<b) return 0;
	return ((zyo[a]*rz[b]%mo)*rz[a-b])%mo;
}
vector<int> so;
bool used[100100];
int main()
{
	int n,m;cin>>n>>m;lint out=1;
	zyo.pb(1);
	rep(i,100100){
		zyo.pb((zyo[i]*(i+1))%mo);
	}
	rep(i,100100) rz.pb(invMod(zyo[i],mo));
	REP(i,2,100100){
		if(!used[i]) so.pb(i);
		for(int j=i+i;j<100100;j+=i) used[j]=true;
	}
	rep(i,so.size()){
		int t=0;
		while(m%so[i]==0){
			t++;m/=so[i];
		}
		if(t>0){
			out*=co(n+t-1,t);out%=mo;
		}
	}
	if(m>1){
		out*=co(n,1);out%=mo;
	}
	cout<<out<<endl;
}

Submission Info

Submission Time
Task D - Factorization
User sky58
Language C++14 (Clang 3.8.0)
Score 400
Code Size 1596 Byte
Status
Exec Time 38 ms
Memory 2548 KB

Test Cases

Set Name Score / Max Score Test Cases
All 400 / 400 0_small_1, 0_small_2, 0_small_3, 1_large_1, 1_large_2, 1_large_3, 2_large_1, 2_large_2, 3_prime_1, 3_prime_10, 3_prime_11, 3_prime_12, 3_prime_13, 3_prime_14, 3_prime_15, 3_prime_16, 3_prime_17, 3_prime_18, 3_prime_19, 3_prime_2, 3_prime_20, 3_prime_21, 3_prime_22, 3_prime_3, 3_prime_4, 3_prime_5, 3_prime_6, 3_prime_7, 3_prime_8, 3_prime_9, 4_hand_1, 4_hand_2, 4_hand_3, sample_01, sample_02, sample_03
Sample 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
0_small_1 38 ms 2548 KB
0_small_2 38 ms 2548 KB
0_small_3 38 ms 2548 KB
1_large_1 38 ms 2548 KB
1_large_2 38 ms 2548 KB
1_large_3 38 ms 2548 KB
2_large_1 38 ms 2548 KB
2_large_2 38 ms 2548 KB
3_prime_1 38 ms 2548 KB
3_prime_10 38 ms 2548 KB
3_prime_11 38 ms 2548 KB
3_prime_12 38 ms 2548 KB
3_prime_13 38 ms 2548 KB
3_prime_14 38 ms 2548 KB
3_prime_15 38 ms 2548 KB
3_prime_16 38 ms 2548 KB
3_prime_17 38 ms 2548 KB
3_prime_18 38 ms 2548 KB
3_prime_19 38 ms 2548 KB
3_prime_2 38 ms 2548 KB
3_prime_20 38 ms 2548 KB
3_prime_21 38 ms 2548 KB
3_prime_22 38 ms 2548 KB
3_prime_3 38 ms 2548 KB
3_prime_4 38 ms 2548 KB
3_prime_5 38 ms 2548 KB
3_prime_6 38 ms 2548 KB
3_prime_7 38 ms 2548 KB
3_prime_8 38 ms 2548 KB
3_prime_9 38 ms 2548 KB
4_hand_1 38 ms 2548 KB
4_hand_2 38 ms 2548 KB
4_hand_3 38 ms 2548 KB
sample_01 38 ms 2548 KB
sample_02 38 ms 2548 KB
sample_03 38 ms 2548 KB