D题
首先有以下性质
1. (a+b)%mod 等价于 a%mod + b%mod
2. a*b%mod 等价于 a%mod*b%mod (仅当a*b没有溢出时)
该题求解gcd(a,b) a是大数
根据辗转相除法
gcd(a,b)=gcd(b,
展开全文
思路先看一眼题，gcd，再看一眼数据，a 的十进制位数最大可以达到1e6！这意味着a可能非常大! ！超过了long long类型所能表示的范围。由于a过大，我们不能直接使用标准的欧几里得算法，因为a无法作为一个long long或者int类型传入计算。核心处理当 a是一个大数时， 欧几里得算法的操作
展开全文
先对大整数取模，再进行辗转相除法
#include <iostream>
#include<string>
using namespace std;
long long mod(const string&s,long long b){
long long r
展开全文
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int
展开全文
//看完题目：哇，这么水！
//看完数据范围：long long 都存不下，该怎么办？
//不过，我突然想到：将a对b取模，就可以存下了，随后便可用__gcd()计算
//完整代码如下，第16行是取模部分
#include<bits/stdc++.h>
#define int long
展开全文
算法思想
由于 的位数最大可达 ，无法直接存储为普通整数，而 在常规整数范围内。计算 可利用欧几里得算法的性质：
因此只需先求出 ，之后再用常规的欧几里得算法计算两数的最大公约数。
可通过模拟大数取模的过程：从左到右逐位处理，用当前余数 更新为
最终 即为所求余数。
代码实现
#in
展开全文
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
string a;
ll b;
cin>>a>>b;
ll res
展开全文
由于精度问题,必须要开longlong,其实核心代码很简单
#include <bits/stdc++.h>
using namespace std;
int main() {
string sa;
long long a = 0, b;
cin >>
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
