首页 > 代码库 > 深坑之---数学
深坑之---数学
本学期的数学生涯正式开始，第一个进军的毫无疑问是数论。
现在还属于学习和消化阶段，写这样零散地整理知识点，以后再总结。
1. 模算术 （ 快速幂取模 ）
//在O(logn)的时间复杂度完成 a^b % m 的计算//另外还有模算术(a+b)%c =( a%c + b%c ) %c(a-b)%c =( a%c - b%c + c) %c(ab)%c = (a%c)(b%c) % c
LL fast_mod(LL a,LL b,LL n){ LL ans = 1; while(b) { if(b&1) ans = ans*a % n; a = (a%n) * (a%n) % n; b >>= 1; } return ans;}
先记录下我做的两道题目
a.HDU 3003 简直不能再坑，题目读了老半天还是没搞懂题目的意思。。。。题目大意:
一种动物有n层皮肤，每层皮肤都有两种状态，透明或者不透明，透明的皮肤光照一天变为不透明，不透明的皮肤光照一天变为透明
光可以透过透明的皮肤照射到下一层。 刚出生的动物所有层的皮肤都是不透明的，每层皮肤都变过透明，则这只动物长大成人。(特别注意是变过，，而不是所有成都一起变透明)
问，给定一个N，表示N层皮肤，问第几天可以长大成人，得数MOD上N、
题解：
如果这样的话，可以推算出公式 ans = 2^(n-1) + 1 结果 mod n， 那么，这题就是一个很裸很裸的快速幂取模了。。
1 /* *********************************************** 2 Problem :HDU3003 3 File Name : 4 Author : 5 Created Time :2014-09-09 20:29:58 6 ************************************************ */ 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm>10 typedef long long LL;11 using namespace std;12 int n;13 14 LL fast_mod(LL a,LL b,LL n)15 {16 LL ans = 1;17 while(b)18 {19 if(b&1) ans = ans*a % n;20 a = (a%n) * (a%n) % n;21 b >>= 1;22 }23 return ans;24 }25 26 int main()27 {28 while(~scanf("%d",&n) && n)29 {30 int ans = (fast_mod(2,n-1,n) + 1 ) % n;31 printf("%d\n",ans);32 }33 return 0;34 }
b.Uva11582 - Colossal Fibonacci Numbers! ( 快速幂取模 + 打表 ) 题目大意:
对于斐波那契数列来说，f[i] = f[i-1] + f[i-2];
现在问对于一个很大的数num = a^b ， f[num] % n等于多少。
输入 a b n 输出 f[num] % n
题解：
因为全部是对n取模
令F[i] = f[i]%n
余数最多有n种，所以循环节最长是n^2，紫书是这样说的，具体证明不会。
1 /* *********************************************** 2 Problem :11582 - Colossal Fibonacci Numbers! 3 File Name : 4 Author : 5 Created Time :2014-09-09 20:29:58 6 ************************************************ */ 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm>10 #include <vector>11 using namespace std;12 typedef unsigned long long ull;13 14 vector<int> fib[1005];15 int period[1005];16 int t,n;17 ull a, b;18 19 void init()20 {21 for(int i=2;i<=1000;i++)22 {23 fib[i].push_back(0);24 fib[i].push_back(1);25 for(int j=2;;j++)26 {27 int t = (fib[i][j-1] % i + fib[i][j-2] % i) % i;28 fib[i].push_back(t);29 if(fib[i][j] == 1 && fib[i][j-1] == 0) //出现循环节,总数为j-130 {31 period[i] = j - 1;32 break;33 }34 }35 }36 }37 38 int q_pow_mod(ull a,ull b,int m)39 {40 int ans = 1;41 while(b)42 {43 if(b&1) ans = (int)((ans*a) % m);44 a = (a%m) * (a%m) % m;45 b >>= 1;46 }47 return ans;48 }49 50 int main()51 {52 freopen("1.txt","r",stdin);53 init();54 scanf("%d",&t);55 while(t--)56 {57 scanf("%llu %llu %d",&a,&b,&n);58 if(a == 0 || n == 1) printf("0\n");59 else60 {61 int k = q_pow_mod(a%period[n], b, period[n]);62 printf("%d\n",fib[n][k]);63 }64 }65 return 0;66 }
深坑之---数学
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。