图片转自
找出比自己大且欧拉函数也比自己大的第一个数
很巧妙, 找比自己大的第一个质数就可以， 因为质数x, ϕ ( x ) = x − 1 phi(x) = x-1 ϕ(x)=x−1
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 5;
int prime[maxn];void doprime(){memset(prime,0,sizeof(prime));prime[1]=1;for(int i=2;i*i<maxn;i++){if(!prime[i]){for(int j=2*i;j<maxn;j+=i){prime[j]=1;}}}
}int solve(int n){for(int i=n+1;;i++){if(!prime[i])return i;}
}int main(){int t,n,num,cas=1;doprime();cin>>t;while(t--){long long ans = 0;cin>>n;for(int i=0;i<n;i++){cin>>num;ans += solve(num);}///Case 1:22cout<<"Case "<<cas++<<": "<<ans<<" Xukha"<<endl;}
}找出所有的约数对数, 并且满足对内的元素不小于b
步骤：
#include<iostream>
#include<cstring>
#include<algorithm>
#define dbg(a) cout<<#a<<" : "<<a<<endl
using namespace std;typedef long long LL;
typedef pair<LL, int> PII;
const int N = 1000010;int primes[N];
int cnt;
int cntf, cntd;
LL divisor[N];
PII factor[N];
bool st[N];// 筛质数
void init() {for(int i = 2; i < N; i ++){if(!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] * i < N; j ++) {st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}void dfs(LL u, LL p){if(u > cntf) {divisor[cntd ++] = p;return;}for(int i = 0; i <= factor[u].second; i ++) {dfs(u + 1, p);p = (LL) p * factor[u].first;}
}int main(){init();int T;cin >> T;for(int k = 1; k <= T; k ++) {cntd = cntf = 0;LL a, b;cin >> a >> b;if(a< b * b) {printf("Case %d: 0n", k);continue;}printf("Case %d: ", k);LL sum = 1;// 质因子分解for(int i = 0; primes[i] <= a / primes[i]; i ++) {LL p = primes[i];if(a % p == 0) {LL s = 0;while(a % p == 0) {a /= p;s ++;}factor[++ cntf] = {p, s};sum = (LL)sum * (s + 1);}}if(a > 1) {factor[++ cntf] = {a, 1};sum = (LL)sum *(1 + 1);}sum /= 2;//筛约数dfs(1, 1);sort(divisor, divisor + cntd);for(int i = 0; i < cntd; i ++) {if(b <= divisor[i]) break;sum --;}printf("%lldn", sum);}return 0;}太妙了，简直就是妙蛙种子吃着妙脆角妙进了米奇妙妙屋.
看大佬博客的。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>using namespace std;typedef long long LL;LL qmi(LL a, LL b, LL p) {LL res = 1;while(b) {if(b & 1) res = (LL)res * a % p;a = (LL) a * a % p;b >>= 1;}return res;
}int main() {int T;cin >> T;for(int i = 1; i <= T; i ++) {LL n, k;cin >> n >> k;LL trail = qmi(n, k, 1000);double x, y;y = modf((double) k * log10(n), &x);LL lead = pow(10, y) * 100;printf("Case %d: %03lld %03lldn",i, lead,trail);}return 0;
}又是质因子分解咯
N = p 1 c 1 ∗ p 2 c 2 ∗ . . . ∗ p k c k N = p_1^{c1} * p_2^{c2} * ...* p_k^{c_k} N=p1c1∗p2c2∗...∗pkck
要想化成 b a b^a ba ，则 N = ( p 1 c 1 / a ∗ p 2 c 2 / a ∗ . . . ∗ p k c k / a ) a N = (p_1^{c1/a} * p_2^{c2/a} * ...* p_k^{c_k/a})^a N=(p1c1/a∗p2c2/a∗...∗pkck/a)a
则求 a = g c d ( c 1 , c 2 , c 3 , . . . , c k ) a = gcd(c1, c2, c3, ..., ck) a=gcd(c1,c2,c3,...,ck)即可
注意当是负数的时候要特殊处理, 则幂 a a a 不能是偶数
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 100010;int primes[N];
bool st[N];
int cnt;void init() {for(int i = 2; i < N; i ++){if(!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] * i < N; j ++) {st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}int gcd(int a, int b){return b?gcd(b, a % b):a;
}
int main() {init();int T;scanf("%d", &T);for(int k = 1; k <= T; k ++) {int n;int f = 0;scanf("%d", &n);if(n < 0) {n = -n, f = 1;}int d = 0;for(int i = 0; i < cnt; i ++) { // primes[i] < n / primes[i]也可if(n % primes[i] == 0) {int s = 0;while(n % primes[i] == 0) {s ++, n /= primes[i];}if(d == 0) d = s;else d = gcd(d, s);}}if(n > 1) d = gcd(d, 1);if(f) {while(d % 2 == 0) d >>= 1;}printf("Case %d: %dn",k, d);}return 0;}结论题咯。
N较小，暴力求解。
N较大， a n s = l o g ( n ) + C + 1.0 / ( 2 ∗ n ) , ( C = 0.57721566490153286060651209 ) 欧 拉 常 数 ans = log(n) + C + 1.0/(2 * n), (C = 0.57721566490153286060651209) 欧拉常数 ans=log(n)+C+1.0/(2∗n),(C=0.57721566490153286060651209)欧拉常数
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>using namespace std;const int N = 100010;
const double r = 0.57721566490153286060651209;
double s[N];int main() {for(int i = 1; i < N; i ++) {s[i] = s[i - 1] + 1.0 / i;}int T;scanf("%d", &T);for(int t = 1; t <= T; t ++) {int n;scanf("%d", &n);if(n < N) printf("Case %d: %.10fn",t, s[n]);else printf("Case %d: %.10fn", t, log(n) + r + 1.0/(2 * n));}return 0;
}大数除法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>using namespace std;
typedef long long LL;int main(){int T;scanf("%d", &T);for(int k = 1; k <= T; k ++) {vector<int> A;string str;cin >> str;LL b;cin >> b;if(b < 0) b = -b;for(int i = 0; i < str.size(); i ++) {if(str[i] == '-') continue;else A.push_back(str[i] - '0');}LL t = 0;for(int i = 0; i < A.size(); i ++) {t = t * 10 + A[i];t %= b;}if(t == 0) printf("Case %d: divisiblen", k);else printf("Case %d: not divisiblen", k);}return 0;
}import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner s = new Scanner(System.in);int t = s.nextInt();int cas=1;while(t-->0){BigInteger a = s.nextBigInteger();BigInteger b = s.nextBigInteger();b=b.abs();d(b)==BigInteger.ZERO){System.out.println("Case "+cas+": "+"divisible");cas++;}else{System.out.println("Case "+cas+": "+"not divisible");cas++;}}}
}
二次筛法咯。
线性筛 + 埃氏筛法
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1000010;
int primes[N];
int cnt;
bool st[N];typedef long long LL;void init(int n) {memset(st, 0, sizeof st);cnt = 0;for(int i = 2; i < N; i ++) {if(!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] * i < N; j ++) {st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}
int main() {int T;init(50000);scanf("%d", &T);for(int k = 1; k <= T; k ++) {int l, r;scanf("%d%d", &l, &r);memset(st, false, sizeof st);for(int i = 0; i < cnt; i ++) {LL p = primes[i];// 二次筛,筛区间质数, 这里要p*2, 防止结果l等于p，把p也给筛咯for(LL j = max((l + p - 1) / p * p, p * 2); j <= r; j += p)//偏移量, 若太大存不住st[j - l] = true;}cnt = 0;for(int i = 0; i <= r - l; i ++) {// 把1情况去掉if(!st[i] && i + l >= 2)cnt ++;}printf("Case %d: %dn", k, cnt);}return 0;
}N！中分解质因子 其中的 5 k 5^k 5k, 质因子5的幂k有多大, 则后面就有多少个0
类似阶乘分解的题。
即 N ! N! N!, 计算其中质因子5的幂。
利用 下面代码计算N!中, p的幂s
for(LL i = n; i; i /= p) {s += i / p;}
然后利用二分来枚举最优解咯
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;typedef long long LL;LL num;LL solve(LL n) {LL s = 0;for(LL i = n; i; i /= 5) {s += i / 5;}return s;
}int main() {int T;scanf("%d", &T);for(int t = 1; t <= T; t ++) {scanf("%lld", &num);LL l = 1, r = 1e12;while(l < r) {int mid = l + r >> 1;if(solve(mid) >= num) r = mid;else l = mid + 1;}if(solve(l) == num)printf("Case %d: %lldn", t, l);else printf("Case %d: impossiblen", t);}return 0;
}求最小x满足, a x + b ≡ c ( m o d 2 k ) ax + b equiv c (mod 2^k) ax+b≡c (mod 2k)
a + c x = b + y ∗ 2 k a + cx = b + y*2^k a+cx=b+y∗2k
c x − 2 k ∗ y = b − a cx - 2^k*y = b - a cx−2k∗y=b−a
c x + 2 k ∗ y ′ = b − a cx + 2^k*y' = b - a cx+2k∗y′=b−a
用扩展欧几里得算法求即可
a x + b y = g c d ( a , b ) ax + by = gcd(a,b) ax+by=gcd(a,b)通解:
{ x = x 0 + b g c d ( a , b ) ∗ t y = y 0 − a g c d ( a , b ) ∗ t left{ begin{aligned} & x = x_0 + frac{b}{gcd(a, b) } * t \ & y = y_0 - frac{a}{gcd(a, b)} * t end{aligned} right. ⎩⎪⎪⎨⎪⎪⎧x=x0+gcd(a,b)b∗ty=y0−gcd(a,b)a∗t
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL &x, LL &y) {if(!b) {x = 1, y = 0;return a;}LL x1, y1;LL d = exgcd(b, a % b, x1, y1);x = y1;y = x1 - a / b * y1;return d;}
int main() {LL a, b, c, k;while(~scanf("%lld%lld%lld%lld", &a, &b, &c, &k) && a + b + c + k) {LL z = (LL)1 << k;LL x, y;LL d = exgcd(c, z, x, y);LL p = b - a;if(p % d != 0) puts("FOREVER");else {x = (LL)x * (p / d);LL t = z / d;x = (x % t + t) % t;printf("%lldn", x);}}return 0;
}扩展欧几里得+区间交集+细节处理
代码转自：xzx9
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x1,x2,y1,y2;
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(!b){x=1;y=0;return a;}ll ans=exgcd(b,a%b,x,y);ll tmp=x;x=y;y=tmp-(a/b)*y;return ans;
}
ll cal(ll a,ll b,ll c)
{ll x,y;ll gcd=exgcd(a,b,x,y);if(c%gcd)return 0;x=x/gcd*c;y=y/gcd*c;int t1 = b / gcd;int t2 = a / gcd;//左边界上取整,右边界下取整ll r1=floor(1.0*(x2-x)/t1);ll l2=ceil(1.0*(y-y2)/t2);ll l1=ceil(1.0*(x1-x)/t1);ll r2=floor(1.0*(y-y1)/t2);//区间内交集ll l=max(l1,l2);ll r=min(r1,r2);return l<=r?r-l+1:0;
}
int main()
{ll a,b,c,ans=0; scanf("%lld%lld%lld",&a,&b,&c);scanf("%lld%lld",&x1,&x2);scanf("%lld%lld",&y1,&y2);if(c>0)//预处理方便处理c=-c,a=-a,b=-b;if(a<0)a=-a,swap(x1,x2),x1=-x1,x2=-x2;if(b<0)b=-b,swap(y1,y2),y1=-y1,y2=-y2;if(x1>x2||y1>y2)//分类讨论ans=0;if(a==0&&b==0){if(c==0)ans=(x2-x1+1)*(y2-y1+1);}else if(a==0){ll t=-c/b;if(b*t+c==0&&t>=y1&&t<=y2)ans=x2-x1+1;}else if(b==0){ll t=-c/a;if(a*t+c==0&&t>=x1&&t<=x2)ans=y2-y1+1;}elseans=cal(a,b,-c);printf("%lldn",ans);return 0;
}
预处理前缀和咯
注意：
#include<iostream>
using namespace std;const int N = 1e5 + 10;
int sum[N];bool is_prime(int x) {for(int i = 2; i * i <= x; i ++)if(x % i == 0) return false;return true;
}void init() {for(int i = 0; i <= 10010; i ++) {if(!i) {sum[i] = 1; continue;}if(is_prime(i * i + i + 41)) {sum[i] = sum[i - 1] + 1;}else sum[i] = sum[i - 1];}
}int main() {init();int l, r;while(~scanf("%d%d", &l, &r)) {double ans;if(l == 0) {ans = 100 * (sum[r]) * 1.0 / (r + 1);}else {ans = 100 * (sum[r] - sum[l - 1]) * 1.0 / (r - l + 1);}printf("%.2fn", (double) ans + 1e-8);}return 0;
}
看一会就知道规律了咯
就是筛欧拉函数模板题咯
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;
typedef long long LL ;
const int N = 1000010;int primes[N];
bool st[N];
int cnt;
LL sum[N];
LL phi[N];typedef long long LL;void init() {phi[1] = 1;for(int i = 2; i < N; i ++) {if(!st[i]) {primes[cnt ++] = i;phi[i] = i - 1;}for(int j = 0; (LL)primes[j] * i < N; j ++) {int t = primes[j] * i;st[t] = true;if(i % primes[j] == 0) {phi[t] = phi[i] * primes[j];break;}phi[t] = phi[i] * (primes[j] - 1);}} for(int i = 1; i < N; i ++)sum[i] = sum[i - 1] + phi[i];
}int main() {int n;init();while(~scanf("%d", &n) && n) {printf("%lldn", sum[n] - 1);}return 0;
}本文发布于:2024-02-02 11:00:50，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170684285143352.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
