数论 数学    发布于 2019-11-06   421人围观   0条评论

题解

第一问快速幂

第二问是扩展欧几里得算法求不定方程

第三问使用BSGS算法求离散模对数

三个函数直接看代码吧……纯板子题……

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get_num(){
    ll num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
ll y,z,p;
map<ll,ll>mp;
ll quick_pow(ll a,ll b,ll mod){
    ll ret = 1;
    while(b > 0){
        if(b & 1){
            ret = ret * a;
            ret %= mod;
        }
        b >>= 1;
        a = a * a;
        a %= mod;
    }
    return ret;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(b == 0){
        d = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,d,x,y);
    ll tp = x;
    x = y;
    y = tp - (a / b) * y;
    return;
}
void BSGS(ll y,ll z,ll p){
    mp.clear();
    y %= p;
    if(y == 0 && z == 0){
        cout << "1" 
查看更多
NTT 数学 组合数 生成函数    发布于 2019-10-12   158人围观   0条评论

图片标题

题解

首先声明……其实我们的答案跟Wi没太大关系,这一部分只需要在最后的时候对应乘上即可,此题最核心的部分是计算选择了i种颜色的方案数。
首先我们来看如果我们选择了i种颜色使它们恰好出现了S次,那么选择颜色种类的方案数即为Cmi,然后我们去用这i个颜色涂这n个位置的时候,实际上就是一个可重排列的计算数,方案总数为n!(S!)i(niS)!,然后剩下的位置任意涂色,一共还剩n-i*S个位置,每个位置有m-i种颜色选择,所以方案数为(mi)niS
我们记fi=Cmin!(S!)i(niS)!(mi)niS
然而这并不是恰好有i种颜色恰好都出现k次。实际上在我们在后面自由涂色的时候,我们依旧有可能会将一种颜色涂成恰好出现k次。
So……这时候我们就用到容斥原理了。假设ansi为恰好i种颜色都恰好出现k次,由容斥原理有:
ansi=j=imin(m,n/S)(1)jiCjifjj

查看更多
NTT 数学 组合数    发布于 2019-10-12   194人围观   0条评论
#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int maxm = 1e5+5;
const int maxn = 1e7+5;
typedef long long ll;
const ll mod = 1004535809;
ll fac[maxn],inv[maxn],w[maxm],f[maxm<<2],finv[maxn];
ll b[maxm<<2];
int rev[maxm<<2];
void init(int x){
    fac[0] = fac[1] = inv[0] = inv[1] = finv[0] = finv[1] = 1ll;
    for(int i = 2;i <= x;++i){
        fac[i] = fac[i-1] * i % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        finv[i] = finv[i-1] * inv[i] % mod;
    }
    return;
}
ll quick_pow(ll a,ll b,ll mod){
    ll ret = 1;
    while(b){
        if(b & 1)
            ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}
ll g;
int len,lg;
void NTT_init(int k){
    len = 1;lg = 0;
    for(len = 1;len < k;len <<= 1,lg++);
    for(int i = 0;i < len;++i)
        rev[i] = (rev[i>>1]>>1) | ((i & 1) << (lg - 1));
}
void NTT(ll *a,int len,int f){
    for(int i = 0;i < len;++i){
        if(i < rev[i])
            swap(a[i],a[rev[i
查看更多
模拟 数学    发布于 2017-01-31   334人围观   1条评论

A. k-th divisor

 

You are given two integers n and k. Find k-th smallest divisor of n, or report that it doesn't exist.

Divisor of n is any such natural number, that n can be divided by it without remainder.

Input

The first line contains two integers n and k (1 ≤ n ≤ 10151 ≤ k ≤ 109).

Output

If n has less than k divisors, output -1.

Otherwise, output the k-th smallest divisor of n.

Examples
input
4 2
output
2
input
5 3
output
-1
input
12 5
output
6
Note

In the first example, number 4 has three divisors: 12 and 4. The second one is 2.

In the second example, number 5 has only two divisors: 1 and 5. The third divisor doesn't exist, so the answer is -1.

题目大意:给出两个数n和k,求n的第k个因数,数据范围都看得懂……特别的,如果n没有第k个因数,就输出-1

不得不说CF的题目坑爹啊,非得用I64d或者流输入输出。。

这道题如果直接暴力枚举的话,会TLE的。。

所以根据某数学结论,我们可以在sqrt(n)内枚举n的因数,然后对应到后面的因数去。。。

然后两边都用vector存好了,因为vector是动态分配空间,不至于MLE,然后就在前sqrt(n)内暴力瞎搞就行了。。(我觉得还可以写内存池,不过太麻烦了)

这是一道好题。。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace s
查看更多