洛谷-数学1-基础数学问题6

P2660 zzc 种田题目背景可能以后 zzc 就去种田了。题目描述田地是一个巨大的矩形然而 zzc 每次只能种一个正方形,而每种一个正方形时 zzc 所花的体力值是正方形的周长种过的田不可以再种zzc 很懒还要节约体力去泡妹子想花最少的体力值去种完这块田地问最小体力值。输入格式两个正整数 x,y表示田地的长和宽。输出格式输出最小体力值。输入输出样例输入 #1复制1 10输出 #1复制40输入 #2复制2 2输出 #2复制8说明/提示1≤x,y≤1016。实现代码#includebits/stdc.h using namespace std; int main(){ long long x,y,ans0; cinxy; while(xy){ swap(x,y); ans4*y*(x/y); x%y; } coutans; return 0; }P3601 签到题题目背景这是一道签到题建议做题之前仔细阅读数据范围题目描述我们定义一个函数qiandao(x) 为小于等于 x 的数中与 x不互质的数的个数。这题作为签到题给出 l 和 r求出il∑r​qiandao(i)mod666623333输入格式一行两个整数l、r。输出格式一行一个整数表示答案。输入输出样例输入 #1复制233 2333输出 #1复制1056499输入 #2复制2333333333 2333666666输出 #2复制153096296说明/提示对于 30% 的数据l,r≤103。对于 60% 的数据l,r≤107。对于 100% 的数据1≤l≤r≤1012r−l≤106。实现代码#include iostream #include cstdio #include cstring #include cstdlib #include cmath #define MAXN 1000005 #define MOD 666623333 using namespace std; long long l,r,ans,BASE; int cnt; bool isprime[MAXN]; long long prime[MAXN],A[MAXN],B[MAXN]; void shai() { for(int i2;iMAXN;i) { if(!isprime[i]) prime[cnt]i; for(int j2*i;jMAXN;ji) isprime[j]1; } } void work() { int i1; while(prime[i]*prime[i]r) { long long pprime[i]; for(int x(p-l%p)%p;xr-l;xp) { A[x]/p,A[x]*p-1; while(B[x]%p0) B[x]/p; }i; } } int main() { shai(); scanf(%lld%lld,l,r);BASEl; for(long long il;ir;i) A[i-BASE]i,B[i-BASE]i; work(); for(int i0;ir-l;i) { if(B[i]!1) A[i]/B[i],A[i]*(B[i]-1); ans(ansiBASE-A[i])%MOD; } printf(%lld,ans); return 0; }P1403 [AHOI2005] 约数研究题目描述科学家们在 Samuel 星球上的探险得到了丰富的能源储备这使得空间站中大型计算机 Samuel II 的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩小联被允许用 Samuel II 进行数学研究。小联最近在研究和约数有关的问题他统计每个正数 N 的约数的个数并以 f(N) 来表示。例如 12 的约数有 1,2,3,4,6,12因此 f(12)6。下表给出了一些 f(N) 的取值N123456f(N)122324现在请你求出i1∑n​f(i)输入格式输入一个整数 n。输出格式输出答案。输入输出样例输入 #1复制3输出 #1复制5说明/提示对于 20% 的数据N≤5000对于 100% 的数据1≤N≤106。实现代码#includecstdio int n,ans; int main(){ scanf(%d,n); for(int i1,j;in;ij1){ jn/(n/i); ans(n/i)*(j-i1); } printf(%d,ans); return 0; }P1593 因子和题目描述输入两个整数 a 和 b求 ab 的因子和。由于结果太大只要输出它对 9901 取模的结果。输入格式仅一行为两个整数 a 和 b。输出格式输出一行一个整数表示答案对 9901 取模的结果。输入输出样例输入 #1复制2 3输出 #1复制15说明/提示数据规模与约定对于全部的测试点保证 1≤a≤5×1070≤b≤5×107。实现代码#includeiostream #includecstdio #define mod 9901 using namespace std; int a,b,sa,n[10010][2],cot0,ans1; int quick_pow(int ml,int nl) { int s1; while(nl0) { if(nl%21) { s(s%mod)*(ml%mod)%mod; } mlml*ml%mod; nlnl1; } return s%mod; } int sum(int x,int y) { int k0; yy*b; if(x%mod1) { k(y1)%mod; } else { k(quick_pow(x%mod,y1)-1)%mod*quick_pow((x-1)%mod,mod-2)%mod; } return k%mod; } int main() { scanf(%d%d,a,b); if(a0) { printf(0\n); return 0; } for(int i2;i*ia;i) { if(a%i0) { cot; n[cot][0]i; n[cot][1]1; aa/i; while(a%i0) { n[cot][1]; aa/i; } } } if(a!1) { cot; n[cot][0]a; n[cot][1]1; } for(int i1;icot;i) { ansans*sum(n[i][0],n[i][1])%mod; } printf(%d\n,(ans%modmod)%mod); return 0; }