首页 > 其他 > 详细

数学一些笔记

时间:2019-04-20 20:46:40      阅读:162      评论:0      收藏:0      [点我收藏+]

                                   数学篇

大概主要刷uva,写题解吧

  1. 巨大的斐波纳契:题目概述:Input begins with an integer t ≤ 10, 000, the number of test cases. Each test case consists of three integers a, b, n where 0 ≤ a, b < 2 64 (a and b will not both be zero) and 1 ≤ n ≤ 1000.

因为是有周期的,所以用快速幂求出来第几个数

#include <bits/stdc++.h>

using namespace std;

#define ll unsigned long long

ll a[102000];

ll M;

ll pw(ll x,ll y,ll p){

       //pow(x,y)%p

       ll re =1%p;//p要是等于1,不就=0了

       for(;y>0;y/=2){//快速幂就是转二进制,除2

              if(y%2==1){//判断是否为奇数

                     re=re*x%p;//计数就是这样re=re*x%p;

              }

              x=x*x%p;//偶数就是x*x%p

       }

       return re;

}

void fbn(ll p){

       for(int i=3;i<=p*p+10;i++){

              a[i]=a[i-1]+a[i-2];

              a[i]%=p;

              if(a[i]==a[2]&&a[i-1]==a[1]) {

              M=i-2;break;

              }

       }

}

int n;

int main(){

       a[1]=1;

       a[2]=1;

       cin>>n;

       for(int i=1;i<=n;i++){

       ll x,y,p;

       cin>>x>>y>>p;

       if(p==1||!x){printf("0\n");

       continue ;}

       fbn(p);

             ll m=pw(x%M,y,M);

             printf("%llu\n",a[m]);}}

2.  uva 12169 - Disgruntled Judge

暂时略

3.10375 - Choose and divide

The binomial coefficient C(m, n) is defined as

C(m, n) = m! /(m − n)! n!

#include <bits/stdc++.h>

using namespace std;

  int main()

  { int p, q, r, s;

while (~scanf("%d%d%d%d", &p, &q, &r, &s)){

          double ans = 1.0;

         for (int i = 1, j = p-q+1, x = 1, y = r-s+1; i <= q || x <= s;)

        {if (i <= q)    ans *= (double)(j++)/(i++);

 if (x <= s)    ans *= (double)(x++)/(y++);       

         }         printf("%.5lf\n", ans);      } }

 

 

 

3. Minimum Sum LCM uva 10791

The input file contains at most 100 test cases. Each test case consists of a positive integer N (1 ≤ N ≤ 2 31 − 1). Input is terminated by a case where N = 0. This case should not be processed. There can be at most 100 test cases. Output

Output of each test case should consist of a line starting with ‘Case #: ’ where # is the test case number. It should be followed by the summation as specified in the problem statement. Look at the output for sample input for details

大概就是给你一个数,让你从中选择两个质因数,相加最大,不能发现只要因子出现1次,相加即可。坑在于1和素数要特判

1=1+1;素数=1+自己;

我们可以把一个数进行分解,判断这个数等不等于原来的数,如果一样就是素数

int n, cas = 1;

       while(scanf("%d", &n), n)

       {

              int m = sqrt(n+0.5);

              int t = n, num = 0;

              LL ans = 0;

              for(int i=2; i<=m; i++)   //分解这个数

                     if(t%i == 0)

                     {

                            num++;   //记录质因子的个数

                            int tmp = 1;

                            while(t%i==0)

                            {

                                   tmp*=i;

                                   t/=i;

                                  

                            }

                            ans+=tmp;

                     }

              if(n==t)  //本身为素数时

                     ans = (LL)n + 1;   //必须要加个(LL)

              else if(num == 1||t!=1)  // 单质因子或是剩下一个大于sqrt(n)的质因子的情况

                     ans += t; // 单质因子情况下t为1,剩余一个大于sqrt(n)质因子时t为剩余质因子

              printf("Case %d: %lld\n", cas++, ans);

       }

       return 0;

}

 

  1. 求众数

摩尔投票法:#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll a[2000020];

int main(){

    int n;

    cin>>n;

    int ans=0,js=0;

    int ls;

    for(int i=1;i<=n;i++){

cin>>ls;if(js==0){ans=ls;

       }if(ans==ls){js++;}

       if(ans!=js){ js--;}}cout<<ans<<endl;}

 

  1. 位运算

链接:https://ac.nowcoder.com/acm/contest/549/D
来源:牛客网

位运算是一个非常重要的东西。而小A最近在学习位运算,小A看到了一道很简单的例题,是说从N个数里面选出N-1个数要让它们或起来的值最大,小A想知道这个答案是多少。你可以帮帮他吗?

#include<bits/stdc++.h>

using namespace std;

int a[5000005];

int main(){

    int n;

    scanf("%d",&n);

    for(int i=0;i<n;i++)

        scanf("%d",&a[i]);

    sort(a,a+n);

    long long s=a[2],t;

    for(int i=3;i<n;i++)

        s|=a[i];

    t=s;

    s=max(s|=a[0],t|=a[1]);

    printf("%lld\n",s);

}

 

 

 

 

 

链接:https://ac.nowcoder.com/acm/contest/549/I
来源:牛客网

小A也听说了取石子这个游戏,也决定和小B一起来玩这个游戏。总共有n堆石子,双方轮流取石子,每次都可以从任意一堆中取走任意数量的石子,但是不可以不取。规定谁先取完所有的石子就获胜。但是小A实在是太想赢了,所以在游戏开始之前,小A有一次机会,可以趁小B不注意的时候选择其中一堆石子拿走其中的k个,当然小A也可以选择不拿石子。小A先手。双方都会选择最优的策略,请问在这样的情况下小A有没有必胜的策略,如果有输出YES,否则就输出NO。

#include<bits/stdc++.h>

using  namespace  std;

int main(){

    int n,m;

    cin>>n>>m;

    int ans=0;

    int t;

    for(int i=0;i<n;i++){

        cin>>t;

        ans^=t;

    }

    if(ans==0){

        printf("NO\n");

    }else{

        printf("YES\n");

    }

    return 0;

}

 

矩阵乘法:大家都知道,斐波那契数列是满足如下性质的一个数列:

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

题目描述

 

用矩阵将斐波纳契表示出来,然后再快速幂

#include <bits/stdc++.h>

using namespace std;

int p=1000000007;

void mul(int a[2][2],int b[2][2]){

       int w[2][2]={};

       for(int i=0;i<2;i++){

              for(int j=0;j<2;j++){

                     for(int k=0;k<2;k++){

                            w[i][j]=(w[i][j]+(long long)a[i][k]*b[k][j])%p;

                     }

              }

       }

       memcpy(a,w,sizeof w);

}

int F(long long n){

       int a[2][2]={};

       int b[2][2]={};

       a[0][0]=a[1][1]=1;

       b[0][0]=b[0][1]=b[1][0]=1;

       for(;n;n/=2){

              if(n&1){

                     mul(a,b);

              }

              mul(b,b);

       }

       return a[0][1];

}

int main(){

       long long n;

       cin>>n;

       cout<<F(n)<<endl;

       return 0;

}

 

 

 

 

就是求卡片的非空真子集

f(n)=2**(2*n)-1;

数学一些笔记

原文:https://www.cnblogs.com/AShenSky/p/10742434.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!