P2660 zzc 种田
题目背景
可能以后 zzc 就去种田了。
题目描述
田地是一个巨大的矩形，然而 zzc 每次只能种一个正方形,而每种一个正方形时 zzc 所花的体力值是正方形的周长，种过的田不可以再种，zzc 很懒还要节约体力去泡妹子，想花最少的体力值去种完这块田地，问最小体力值。
输入格式
两个正整数 x,y，表示田地的长和宽。
输出格式
输出最小体力值。
输入输出样例
输入 #1复制
1 10
输出 #1复制
40
输入 #2复制
2 2
输出 #2复制
8
说明/提示
1≤x,y≤1016。
实现代码：
#include<bits/stdc++.h> using namespace std; int main(){ long long x,y,ans=0; cin>>x>>y; while(x&&y){ swap(x,y); ans+=4*y*(x/y); x%=y; } cout<<ans; return 0; }P3601 签到题
题目背景
这是一道签到题！
建议做题之前仔细阅读数据范围！
题目描述
我们定义一个函数：qiandao(x) 为小于等于 x 的数中，与 x不互质的数的个数。
这题作为签到题，给出 l 和 r，求出：
i=l∑rqiandao(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≤1012，r−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 i=2;i<=MAXN;i++) { if(!isprime[i]) prime[++cnt]=i; for(int j=2*i;j<=MAXN;j+=i) isprime[j]=1; } } void work() { int i=1; while(prime[i]*prime[i]<=r) { long long p=prime[i]; for(int x=(p-l%p)%p;x<=r-l;x+=p) { A[x]/=p,A[x]*=p-1; while(B[x]%p==0) B[x]/=p; }i++; } } int main() { shai(); scanf("%lld%lld",&l,&r);BASE=l; for(long long i=l;i<=r;i++) A[i-BASE]=i,B[i-BASE]=i; work(); for(int i=0;i<=r-l;i++) { if(B[i]!=1) A[i]/=B[i],A[i]*=(B[i]-1); ans=(ans+i+BASE-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) 的取值：
| N | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| f(N) | 1 | 2 | 2 | 3 | 2 | 4 |
现在请你求出：
i=1∑nf(i)
输入格式
输入一个整数 n。
输出格式
输出答案。
输入输出样例
输入 #1复制
3
输出 #1复制
5
说明/提示
- 对于 20% 的数据，N≤5000；
- 对于 100% 的数据，1≤N≤106。
实现代码：
#include<cstdio> int n,ans; int main(){ scanf("%d",&n); for(int i=1,j;i<=n;i=j+1){ j=n/(n/i); ans+=(n/i)*(j-i+1); } printf("%d",ans); return 0; }P1593 因子和
题目描述
输入两个整数 a 和 b，求 ab 的因子和。
由于结果太大，只要输出它对 9901 取模的结果。
输入格式
仅一行，为两个整数 a 和 b。
输出格式
输出一行一个整数表示答案对 9901 取模的结果。
输入输出样例
输入 #1复制
2 3
输出 #1复制
15
说明/提示
数据规模与约定
对于全部的测试点，保证 1≤a≤5×107，0≤b≤5×107。
实现代码：
#include<iostream> #include<cstdio> #define mod 9901 using namespace std; int a,b,sa,n[10010][2],cot=0,ans=1; int quick_pow(int ml,int nl) { int s=1; while(nl>0) { if(nl%2==1) { s=(s%mod)*(ml%mod)%mod; } ml=ml*ml%mod; nl=nl>>1; } return s%mod; } int sum(int x,int y) { int k=0; y=y*b; if(x%mod==1) { k=(y+1)%mod; } else { k=(quick_pow(x%mod,y+1)-1)%mod*quick_pow((x-1)%mod,mod-2)%mod; } return k%mod; } int main() { scanf("%d%d",&a,&b); if(a==0) { printf("0\n"); return 0; } for(int i=2;i*i<=a;i++) { if(a%i==0) { cot++; n[cot][0]=i; n[cot][1]=1; a=a/i; while(a%i==0) { n[cot][1]++; a=a/i; } } } if(a!=1) { cot++; n[cot][0]=a; n[cot][1]=1; } for(int i=1;i<=cot;i++) { ans=ans*sum(n[i][0],n[i][1])%mod; } printf("%d\n",(ans%mod+mod)%mod); return 0; }
