数学/神学

Math,math never changs

一反手就是个素数测试模板
http://phoenixgs.cn/2017/06/26/miller-rabin-%e7%ae%97%e6%b3%95/
(反正看不懂那不如直接复制?)

离散对数

#include <bits/stdc++.h>

using namespace std;

long long poww(long long a,long long n,long long mod)
{
    long long ret=1;
    while(n)
    {
        if(n&1)ret=(ret*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ret;
}

long long log_mod(long long a,long long b,long long n)
{
    long long m=(long long)sqrt((double)(n)+0.5);
    long long v=poww(a,n-1-m,n);//a^-m
    long long e=1;
    map<int,int> x;
    x[1]=0;
    
    for(int i=1;i<m;i++)
    {
        e=(e*a)%n;
        if(!x.count(e))x[e]=i;
    }
    
    for(int i=0;i<m;i++)
    {
        if(x.count(b))return i*m+x[b];
        b=(b*v)%n;
    }
    
    return -1;
}

int main()
{
    return 0;
}

狄利克雷卷积
参考:http://blog.csdn.net/hzj1054689699/article/details/75091655
http://blog.csdn.net/Cold_Chair/article/details/73555965
http://blog.csdn.net/mosquito_zm/article/details/76650864

关于卷积的一个血腥的讲解

比如说你的老板命令你干活,你却到楼下打台球去了,后来被老板发现,他非常气愤,扇了你一巴掌(注意,这就是输入信号,脉冲),于是你的脸上会渐渐地(贱贱地)鼓起来一个包,你的脸就是一个系统,而鼓起来的包就是你的脸对巴掌的响应,好,这样就和信号系统建立起来意义对应的联系。下面还需要一些假设来保证论证的严谨:假定你的脸是线性时不变系统,也就是说,无论什么时候老板打你一巴掌,打在你脸的同一位置(这似乎要求你的脸足够光滑,如果你说你长了很多青春痘,甚至整个脸皮处处连续处处不可导,那难度太大了,我就无话可说了哈哈),你的脸上总是会在相同的时间间隔内鼓起来一个相同高度的包来,并且假定以鼓起来的包的大小作为系统输出。好了,那么,下面可以进入核心内容——卷积了!如果你每天都到地下去打台球,那么老板每天都要扇你一巴掌,不过当老板打你一巴掌后,你5分钟就消肿了,所以时间长了,你甚至就适应这种生活了……如果有一天,老板忍无可忍,以0.5秒的间隔开始不间断的扇你的过程,这样问题就来了,第一次扇你鼓起来的包还没消肿,第二个巴掌就来了,你脸上的包就可能鼓起来两倍高,老板不断扇你,脉冲不断作用在你脸上,效果不断叠加了,这样这些效果就可以求和了,结果就是你脸上的包的高度随时间变化的一个函数了(注意理解);如果老板再狠一点,频率越来越高,以至于你都辨别不清时间间隔了,那么,求和就变成积分了。可以这样理解,在这个过程中的某一固定的时刻,你的脸上的包的鼓起程度和什么有关呢?和之前每次打你都有关!但是各次的贡献是不一样的,越早打的巴掌,贡献越小,所以这就是说,某一时刻的输出是之前很多次输入乘以各自的衰减系数之后的叠加而形成某一点的输出,然后再把不同时刻的输出点放在一起,形成一个函数,这就是卷积,卷积之后的函数就是你脸上的包的大小随时间变化的函数。本来你的包几分钟就可以消肿,可是如果连续打,几个小时也消不了肿了,这难道不是一种平滑过程么?反映到剑桥大学的公式上,f(a)就是第a个巴掌,g(x-a)就是第a个巴掌在x时刻的作用程度,乘起来再叠加就ok了,大家说是不是这个道理呢?我想这个例子已经非常形象了,你对卷积有了更加具体深刻的了解了吗?转自GSDzone论坛

康拓展开
参考:http://blog.csdn.net/acdreamers/article/details/7982067
应用1:http://www.acmerblog.com/article-1394075259637-4906.html
应用2:http://blog.csdn.net/lttree/article/details/24909959
补题:http://blog.csdn.net/a601025382s/article/details/38091457
祖传版康拓展开,O(n^2)实现,可以用树状数组降到O(nlogn),然而n!的计算量太庞大感觉没啥意义

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 1e4+11;
typedef unsigned long long ll;
char str[maxn];
ll f[30];
ll fac(ll i){
    return f[i]=i?i*fac(i-1):1;
}
ll cantor(char str[]){
    int len = strlen(str);
    ll ans = 0;
    for(int i = 0; i < len; i++){
        int r = 0;
        for(int j = i+1; j < len; j++){
            if(str[j]<str[i]) r++;
        }
        ans+=r*f[len-i-1];
    }
    return ans;
}
vector<int> v,a;
int arr[20];
void cantor_t(int r,int n){
    r--;
    ll x,t;
    v.clear();a.clear();
    for(int i = 1; i <= n; i++) v.push_back(i);
    for(int i = n; i >= 1; i--){
        t = r/f[i-1];
        r = r%f[i-1];
        a.push_back(v[t]);
        v.erase(v.begin()+t);
    }
}
int main(){
    fac(15);
    cin>>str;
    cout<<cantor(str)<<endl;
    cantor_t(2,5);
    for(int i = 0; i < a.size(); i++) printf("%d",a[i]);cout<<endl;
    return 0;
}

快速的康托逆展开
UVA11525
Si指i后面比它小的个数

#include<bits/stdc++.h>
using namespace std;
#define lowbit(b) (b)&(-b)
const int maxn = 1e6+11;
struct FT{
    int ft[maxn];
    void init(){
        memset(ft,0,sizeof ft);
    }
    int query(int b){
        int sum=0;
        while(b){
            sum+=ft[b];
            b-=lowbit(b);
        }
        return sum;
    }
    void update(int k,int v){
        while(k<maxn){
            ft[k]+=v;
            k+=lowbit(k);
        }
    }
}ft;
bool C(int x,int tmp){
    int sum=ft.query(x);
    return sum>=tmp+1;
}
int ans[maxn];
int main(){
    ios::sync_with_stdio(0);
    int T,k; cin>>T;
    while(T--){
        ft.init();cin>>k;
        for(int i = 1; i <= k; i++) ft.update(i,1);
        for(int i = 1; i <= k; i++){
            int tmp; cin>>tmp;
            int l=1,r=k,mid;
            while(l<r){
                mid=l+r>>1;
                if(C(mid,tmp)) r=mid;
                else l=mid+1;
            }
            ans[i]=l;ft.update(ans[i],-1);
        }
        for(int i = 1; i <= k; i++){
            if(i==k) cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }
    return 0;
}

费马大定理
http://www.cnblogs.com/Inkblots/p/4713808.html

素数
1e2以内有 25 个素数,它们分别是
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97。
1e3以内有 168 个素数,最后几个是
907,911,919,929,937,941,947,953,967,971,977,983,991,997
1e4以内有 1229 个素数,最后几个是
9901,9907,9923,9929,9931,9941,9949,9967,9973
1e5以内有 9592 个素数,最后几个是
99901,99907,99923,99929,99961,99971,99989,99991
1e6以内有 78498 个素数,最后几个是
999907,999917,999931,999953,999959,999961,999979,999983
1e7以内有 664579 个素数,最后几个是
9999901,9999907,9999929,9999931,9999937,9999943,9999971,9999973,9999991
1e8以内有 5761455 个素数,最后几个是
99999931,99999941,99999959,99999971,99999989
1e9以内有 50847534 个素数,最后几个是
999999929,999999937
1e10以内有 455052511 个素数,最后几个是
9999999929,9999999943,9999999967
Fibonacci
http://zhouzixuan.blog.uoj.ac/blog/1313
Fibonacci

标签: 算法, 学习

添加新评论