题目链接:uva 10518 - How Many Calls?
公式f(n) = 2 * F(n) - 1, F(n)用矩阵快速幂求。
#include <stdio.h>
#include <string.h>
long long n;
int b;
struct state {
int s[2][2];
state(int a = 0, int b = 0, int c = 0, int d = 0) {
s[0][0] = a, s[0][1] = b, s[1][0] = c, s[1][1] = d;
}
}tmp(1, 0, 0, 1), c(1, 1, 1, 0);
state count(const state& p, const state& q) {
state f;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
f.s[i][j] = (p.s[i][0] * q.s[0][j] + p.s[i][1] * q.s[1][j]) % b;
return f;
}
state solve(long long k) {
if (k == 0) return tmp;
else if (k == 1) return c;
state a = solve(k / 2);
a = count(a, a);
if (k % 2) a = count(a, c);
return a;
}
int main () {
int cas = 1;
while (scanf("%lld%d", &n, &b), n || b) {
state ans = solve(n);
printf("Case %d: %lld %d %d\n", cas++, n, b,(2 * ans.s[0][0] - 1 + b) % b);
}
return 0;
}
分享到:
相关推荐
How-To Async Calls,vb.net编程语言说明文件。Visual Basic2008.net
java经典的猫叫程序,适合对面向对象概念的深入理解,运行好用
Advanced - Multithreading - How-To Async Calls Advanced - Remoting - How-To TCP Remoting Advanced - Serialization - How-To Serializing Objects Advanced .NET Framework (GDI+) - Animation with GDI+ ...
考虑到经常打电话查询话费使用情况,觉得甚是麻烦,于是就想开发个小程序来简化这个过程,因此就有了下面这个小程序,之所以称之为小程序,是因为它的功能很单一,就是查询话费使用情况和话费余额,但这也是日常生活...
IP话费管理是电信计费系统必备的重要功能模块,主要负责对各种标准的话费进行计算和管理,对通话记录进行添加、修改、查询。本课题以中国电信企业IP话费管理模块作为原型参照,要求对文件存储的用户资料与话单记录...
vk-api-calls 适用于Node.js和io.js的另一个VK API包装器。 :red_exclamation_mark: 尽管此模块在npm上发布并具有版本1,但仍在大量构建中。 请谨慎使用它,或等待本周晚些时候发布的2.0.0 。 特征 简单认证 通过...
026-asynchronous-native-java-calls-spring
babel插件注释纯呼叫 该插件有助于自动#__PURE__注释插入。 它将注释添加到表达式和分配上下文中的新表达式(插件将其视为free副作用)。 这有助于更加有效地执行代码消除,因此可以减少使用者的捆绑包大小。...
高亮函数调用 这个包在函数调用中突出显示函数符号。 这使它们从其他符号中脱颖而出,从而可以轻松查看对其他函数的调用位置。 它还有助于减少拼写错误,因为当您输入函数名称时,如果输入正确,它会带有下划线。...
###polylingual-api-calls 通过建立程序/脚本用于执行API调用不同的语言实验
本书是面向专业程序员和学生的C语言UNIX软件开发指南。 它着重于UNIX系统调用接口。
sportmonks-api-calls 私人德甲经理人游戏对sportmonks API的各种调用。
A Confidence-Guided Automated System for Non-emergency Calls.pdf
"eddturtle/php-async-calls": "dev-master" } 在您的存储库中运行sudo composer update 包含 Composer require "vendor/autoload.php";文件: require "vendor/autoload.php"; 启动一个异步队列: $async = ...
VB.NET - Advanced - Multithreading - How-To Async Calls VB.NET - Advanced - Remoting - How-To TCP Remoting VB.NET - Advanced - Serialization - How-To Serializing Objects VB.NET - Advanced .NET ...
ES6中的Guiles主题电话呼叫 快速的ES6代码,使用Twilio Node.js模块通过电话拨打和接听播放“ Guile主题”的电话。
AngryBirdsStage7
AngryBirdsStage7
AngularJS TodoMVC示例它基于。
Now you don't have to, because this will autocomplete your `imageNamed:` calls like you'd expect. Just type in `[NSImage imageNamed:` or `[UIImage imageNamed:` and all the images in your project will...