NAIPC 2019-It’s a Mod, Mod, Mod, Mod World(类欧几里德模板)

一时失言乱红尘 2023-06-05 12:33 42阅读 0赞

### It’s a Mod, Mod, Mod, Mod World ###

时间限制: 2 Sec 内存限制: 128 MB

#### 题目描述 ####

You are given multiple problems with three integers p, q, and n. Find ![20190401214301_71285.png][]. That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus.

#### 输入 ####

Each input will begin with a line with a single integer W (1≤W≤105 ), which is the number of cases you must solve.  
Each of the next W lines will contain three space-separated integers p, q and n (1≤p, q, n≤106 ),which are the parameters of the problem as described above.

#### 输出 ####

Output W lines, each with the answer for a given instance of the problem, in the order that they appear in the input.

## 样例输入 ##

3
    2 7 2
    1 4 5
    3 8 10

#### 样例输出 ####

6
    7
    37

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn=1e5+7;
     5 const ll mod=1e9+7;
     6 ll p,q,n;
     7 //a 公差 b 首项 c 除数 n 项数
     8 ll work(ll a,ll b,ll c,ll n){
     9     if (n<=0) return 0;
    10     if (n==1) return b/c ;
    11     ll t = 0;
    12     t += a/c*(n-1)*n/2+ b/c*n;
    13     a = a%c;
    14     b = b%c;
    15     if (a==0) return t;
    16     return t+work(c,(a*n+b)%c,a,(a*n+b)/c);
    17 }
    18 int main()
    19 {
    20     int t;
    21     scanf("%d",&t);
    22     while(t--)
    23     {
    24         scanf("%lld%lld%lld",&p,&q,&n);
    25         ll ans=(p*(n+1)*n/2-q*work(p,p,q,n));
    26         printf("%lld\n",ans);
    27     }
    28     return 0;
    29 }

转载于:https://www.cnblogs.com/CharlieWade/p/11469097.html

[20190401214301_71285.png]: http://icpc.upc.edu.cn/upload/image/20190401/20190401214301_71285.png

发表评论取消回复

表情：

评论列表（有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读

相关 GO mod入门

借鉴帖子,特别感谢: 作者：会飞的鲶鱼链接：https://www.jianshu.com/p/c666ebdb462b Go Module是Go官方在1.11

迷南。/ 2023年07月07日 12:55/ 0 赞/ 121 阅读

相关 NAIPC 2019-It’s a Mod, Mod, Mod, Mod World(类欧几里德模板)

It’s a Mod, Mod, Mod, Mod World 时间限制: 2 Sec 内存限制: 128 MB 题目描述 You are given multi

一时失言乱红尘/ 2023年06月05日 12:33/ 0 赞/ 43 阅读

相关 go mod使用

go mod 相关命令 go mod download 下载go.mod文件中指明所有依赖 go mod tidy 整理现有的依赖，删除

野性酷女/ 2022年11月22日 00:11/ 0 赞/ 270 阅读

相关调用apache的mod_status与mod_info模块

httpd.conf中去掉Include的注释： \ Real-time info on requests and configuration Include con

Myth丶恋晨/ 2022年07月19日 02:42/ 0 赞/ 200 阅读

相关 oracle mod函数

mod(m,n) ![这里写图片描述][SouthEast] (1)MOD返回m除以n的余数，如果n是0，返回m。 (2)这个函数以任何数字数据类型或任何非数值型数

冷不防/ 2022年06月13日 05:38/ 0 赞/ 78 阅读

相关 Mod （二分法）

Kim刚刚学会C语言中的取模运算（mod）。他想要研究一下一个数字A模上一系列数后的结果是多少。帮他写个程序验证一下。 Input 第一行一个整数T代表数据组数。接下来

我不是女神ヾ/ 2022年06月09日 04:19/ 0 赞/ 267 阅读

相关 apache限速mod_bw

使用mod\_bandwidth可以实现并发Ip数和带宽的限制，带宽流量控制模块安装 `wget http://bwmod.sourceforge.net/files/m

Bertha 。/ 2022年05月23日 07:24/ 0 赞/ 309 阅读

相关 mod_rewrite

![mod_rewrite-cheat-sheet-v2.png][] ![mod_rewrite.gif][] 转载于:https://www.cnblogs.com/S

淡淡的烟草味﹌/ 2021年12月20日 22:27/ 0 赞/ 323 阅读

相关 Apache Mod_rewrite

<table> <tbody> <tr> <td>目标</td> <td>重写设置</td> <td>说明</td> </tr>

矫情吗；*/ 2021年11月02日 04:10/ 0 赞/ 329 阅读

相关 cgi、fastcig、mod_php、mod_fastcgi、mod_fcgid、php cgi、php fpm关系简介

cgi、fastcgi 是什么 cgi与fastcgi是一种协议规范，其只fastcgi是cgi的等级版 cgi脚本是什么 cgi脚本是一类脚本的统称，比较php

叁歲伎倆/ 2021年10月23日 12:48/ 0 赞/ 361 阅读