1279
备注:
|
← 于2008-02-23 15:35:51修订的的版本9 ⇥
1817
converted to 1.6 markup
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 1: | 行号 1: |
## page was renamed from 程序设计练习20——zju2105——Number Sequence | |
行号 2: | 行号 3: |
http://acm.zju.edu.cn/show_problem.php?pid=2105 |
|
行号 29: | 行号 32: |
------ {{{#!cplusplus /*written by proby*/ #include <iostream> #include <vector> #include <algorithm> using namespace std; //336 is the LCM of all cases vector<int> temList; |
|
行号 30: | 行号 42: |
http://acm.zju.edu.cn/show_problem.php?pid=2105 | int Calc(int a, int b, int n){ if(temList[n] >= 0){ return temList[n]; } if(n==1 || n==2){ temList[n]=1; return temList[n]; } temList[n] = (a*Calc(a, b, n-1) + b*Calc(a, b, n-2))%7 ; return temList[n]; } int MyMod(double n){ while(n > 340){ n-=336; } return int(n); } void MyClear(int& n){ n=-1; } void MyPrint(int n){ cout<<n<<" "; } int main(){ int a, b, res; double n; cin>>a>>b>>n; while(a!=0){ res=MyMod(n); if(temList.capacity() < res+1){ //temList.reserve(res+1); temList.resize(res+1); } for_each(temList.begin(), temList.begin()+res+1, MyClear); //"+1" is very necessary cout<<Calc(a, b, res)<<endl; //for_each(temList.begin(), temList.begin()+res+1, MyPrint); cout<<endl; cin>>a>>b>>n; } return 1; } }}} |
行号 32: | 行号 90: |
#include<iostream>//AC #include<vector> using namespace std; int main() { int A,B; int n; int i,t; t=0; vector<int> a; cin>>A>>B>>n; while(A!=0||B!=0||n!=0) { A=A%7; B=B%7; a.push_back(1); a.push_back(1); for(i=2;i<n;++i) { a.push_back((A*a[i-1]+B*a[i-2])%7); if(a[i]==a[3]&&a[i-1]==a[2]&&i!=3) { t=i-3; break; } } if(t!=0) cout<<a[((n-3)%t)+2]<<endl; else cout<<a[n-1]<<endl; a.clear(); t=0; cin>>A>>B>>n; } return 0; } |
Number Sequence
http://acm.zju.edu.cn/show_problem.php?pid=2105
Time limit: 1 Seconds
Memory limit: 32768K
A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n).
1. Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
2. Output
For each test case, print the value of f(n) on a single line.
3. Sample Input
{{{1 1 3 1 2 10 0 0 0 }}}