Задача 643
Дружественные к 2

Два положительных целых числа $a$ и $b$ являются дружественными к 2, если $\gcd(a,b) = 2^t, t>0$. Например, 24 и 40 являются дружественными к 2, так как $\gcd(24,40) = 8 = 2^3$, в то время как 24 и 36 таковыми не являются, так как $\gcd(24,36) = 12 = 2^2\cdot 3$ не является степенью 2.

Пусть $f(n)$ будет количеством пар положительных целых чисел $(p,q)$ при $1\le p\lt q\le n$, таких что $p$ и $q$ являются дружественными к 2. Известно, что $f(10^2) = 1031$ и $f(10^6) = 321418433$ modulo $1\,000\,000\,007$.

Найдите $f(10^{11})$ modulo $1\,000\,000\,007$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net