题意:PuPu有n层皮肤,每层皮肤都有2种状态:透明和不透明,每层皮肤如果能被太阳照射到,则被太阳照射一天后都会变换状态。PuPu在出生的时候,所有的皮肤都为不透明的,直到每一层的皮肤都有过变为透明状态的时候,PuPu也就长大了。问有n层皮肤的PuPu几天后能长大。
思路:数论。公式推导到最后为 ans = (2^(n-1)+1)%n。所以就用求(num^exp)%MOD的二分算法了,让时间复杂度为0(n)变为0(logn)。
#include<stdio.h>
__int64 n;
__int64 a_b_Mod_c(__int64 a, __int64 b, __int64 c)
{
int digit[64];
int i, k;
__int64 result = 1;
i = 0;
while(b)
{
digit[i++] = b%2; //记下每次二分的状态!0 表示 x^2n=x^n * x^n 1表示x^(2n+1)=x^n * x^n * x;
b >>= 1;
}
for(k = i-1; k >= 0; k--)
{
result = (result * result) % c;
if(digit[k] == 1) //根据二分的结果来算!
{
result = (result * a) % c;
}
}
return result;
}
main()
{
__int64 d;
while(scanf("%I64d",&n),n)
{
d=a_b_Mod_c(2,n-1,n)+1;
printf("%I64d\n",d%n);
}
}
分享到:
相关推荐
杭电ACM分类杭电ACM分类杭电ACM分类杭电ACM分类
杭电离散答案 杭电离散答案 杭电离散答案 杭电离散答案
杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷杭电概率论期末试卷...
考研杭电数据结构试卷
杭电 金工实习报告 杭电 金工实习报告 杭电 金工实习报告
19级学长的杭电计网实验报告,杭电计算机网络实验报告杭电计网实验报告,杭电计算机网络实验报告杭电计网实验报告,杭电计算机网络实验报告杭电计网实验报告,杭电计算机网络实验报告杭电计网实验报告,杭电计算机...
杭电 嵌入式 复习资料 杭电 嵌入式 复习资料杭电 嵌入式 复习资料
杭电计算机考研复试英语问题,共70余题及其自己写的简单回答,本人为杭电计算机2021年上岸考生。
杭电acm 第1090题的.cpp文件
杭电日历----xxyw
杭电数电实验课内题设计答案 (2).pdf杭电数电实验课内题设计答案 (2).pdf杭电数电实验课内题设计答案 (2).pdf杭电数电实验课内题设计答案 (2).pdf杭电数电实验课内题设计答案 (2).pdf杭电数电实验课内题设计答案 (2)...
杭电计组实验9-实现R-I型指令的CPU设计实验.pdf杭电计组实验9-实现R-I型指令的CPU设计实验.pdf杭电计组实验9-实现R-I型指令的CPU设计实验.pdf杭电计组实验9-实现R-I型指令的CPU设计实验.pdf杭电计组实验9-实现R-I型...
杭电研究生入学易班考试题库 杭电研究生入学易班考试题库 杭电研究生入学易班考试题库
杭电计算机组成原理MIPS汇编器模拟器实验6 (2).pdf杭电计算机组成原理MIPS汇编器模拟器实验6 (2).pdf杭电计算机组成原理MIPS汇编器模拟器实验6 (2).pdf杭电计算机组成原理MIPS汇编器模拟器实验6 (2).pdf杭电计算机...
杭电题目acm答案
杭电计算机考研复试七门专业课问题,总结了历届老师问过和自己总结的共400余题及其答案,涵盖所有知识点,本人为杭电计算机2021年上岸考生。
杭电oj1000题解题报告
杭电选课器 杭电选课器 杭电
主要是杭电2044到2050的题目ac代码
杭电题目分类排序列表 包含杭电OJ的部分题目的分类,各种算法的分类题