hdu-5690 All X(快速幂+乘法逆元)
2024-10-19 01:29:03
题目链接:
All X
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
F(x,m) 代表一个全是由数字x组成的m位数字。请计算,以下式子是否成立:
F(x,m) mod k ≡ c
Input
第一行一个整数T,表示T组数据。
每组测试数据占一行,包含四个数字x,m,k,c
每组测试数据占一行,包含四个数字x,m,k,c
1≤x≤9
1≤m≤10^10
0≤c<k≤10,000
Output
对于每组数据,输出两行:
第一行输出:"Case #i:"。i代表第i组测试数据。
第二行输出“Yes” 或者 “No”,代表四个数字,是否能够满足题目中给的公式。
第一行输出:"Case #i:"。i代表第i组测试数据。
第二行输出“Yes” 或者 “No”,代表四个数字,是否能够满足题目中给的公式。
Sample Input
3
1 3 5 2
1 3 5 1
3 5 99 69
Sample Output
Case #1:
No
Case #2:
Yes
Case #3:
Yes
题意:
思路:
m个x组成的数可以表示为x*(1+10+10^2+...+10^m-1)=x*(10^m-1)/9;
即x*(10^m-1)/9%k==c? x*(10^m-1)%(9*k)==9*c?
AC代码:
//#include <bits/stdc++.h> #include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio> using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
//const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const int N=1e5+;
LL x,m,k,c;
LL mod;
LL fastmod(LL x,LL y)
{
LL ans=,base=x;
while(y)
{
if(y&)ans*=base,ans%=mod;
base*=base;
base%=mod;
y=(y>>);
}
return ans;
}
int main()
{
int t,cnt=;
scanf("%d",&t);
while(t--)
{
printf("Case #%d:\n",cnt++);
scanf("%I64d%I64d%I64d%I64d",&x,&m,&k,&c);
mod=*k;
LL fx=fastmod(,m);
LL ans=(fx*x%mod-x%mod)%mod;
if(ans==*c)printf("Yes\n");
else printf("No\n");
} return ;
}
最新文章
- App Store有哪些原因会影响app应用上架呢?(分享)
- 【转】Eclipse Class Decompiler——Java反编译插件
- iFreeThinking - 记录生活,分享思考
- 邻接表实现Dijkstra算法以及DFS与BFS算法
- c#抽象类相关
- ajax请求简写
- 用java获取歌曲文件的专辑封面元信息
- SVN 代码下载,上传
- 漫游Ruby
- c语言结构体4之结构体引用
- AVR32开发环境搭建
- 【最新】让快捷方式 实现相对路径——非.bat方式实现
- Linux:系统的基本优化
- Mac下的效率工具autojump
- 电脑小知识-win10
- 每日Scrum(8)
- 是否要学点GUI编程
- one by one 项目 part 3
- From 百度知道 SQLSERVER 字符集排序规则简单说明
- SQL语句添加删除修改字段